Where it runs
1. The problem
You have a row of tiles. Each tile holds one number: the longest jump forward you may take from it. From a tile with a 3 you can move 1, 2 or 3 tiles ahead. From a tile with a 0 you cannot move at all. You start on the first tile. Can you reach the last one?
Take [2, 3, 1, 1, 4]. From tile 0 you can jump 1 or 2 tiles forward. Jump to tile 1. It holds a 3, and from there you can reach the end. The answer is true.
Now take [3, 2, 1, 0, 4]. However you jump, you cannot get past tile 3, and tile 3 holds a 0. The 4 at the end cannot be reached. The answer is false.
In the last lesson, on making change, you took the best-looking option at each step and showed why that was safe. This is the same greedy approach with a different question: can you reach the end at all?
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- fewest coins or pieces to make an amount
- largest that still fits, taken greedily
- make change with denominations
- prove optimality with an exchange argument
Looks similar, isn't
- Dynamic programming (1-D)
DP keeps every option open until the end. Greedy commits at once and cannot undo.
- Backtracking
Backtracking tries every choice and keeps the best. Greedy tries one and trusts it.
- Sort with a custom comparator
Most greedy solutions begin with a sort. The comparator is where the choice is written.
- Binary search on the answer
There the feasibility test is often greedy itself. The search only picks the value to test.
O(n log n) when the input has to be sorted first. The pass afterwards is a single loop, O(n).
On LeetCode
Jump and coverage problems, where each position lets you reach up to some point and you ask whether you reach the end, or in how few steps. One pass that keeps the furthest reachable spot answers in O(n).
The lesson task, word for word.
Count a jump each time i reaches the end of the current jump's range, and the next range ends at the furthest spot seen so far.
For each start time record how far right a clip reaches, and the counting from Jump Game II gives the fewest clips.
Each tap covers from i minus its range to i plus its range, so record the furthest reach for each left end and count jumps as in Jump Game II.