Lesson 33.2 · Greedy Algorithms
Tracking Reach and Resetting the Start
Keep the farthest point you can reach so far (Jump Game), or restart from the next position whenever a running total goes negative (Gas Station, Kadane).
12 min
Think of it like this
Crossing a river on stepping stones: you don't plan every hop, you just keep track of the farthest stone you could reach from any stone you've stood on. If you ever stand somewhere beyond that, you've fallen in.
1.Farthest reach
Jump Game: walk left to right with reach = max(reach, i + nums[i]); if i ever exceeds reach, you're stuck. Jump Game II counts jumps by treating each range of reachable positions as one BFS level: when you reach the end of the current level, jump once and the new level ends at the farthest reach found.
nums = [2, 3, 1, 1, 4]Step 1/3From index 0 you can reach up to index 2.
2.Reset when the running total fails
Gas Station: if starting at s you run dry before station i, then no start between s and i works either (each would arrive at i with less fuel). So restart at i + 1. If total gas ≥ total cost, the final start works.
Remember
- Farthest reach in one pass.
- Levels of reach = minimum jumps.
- A failing prefix rules out every start inside it.
Common mistakes
- Trying every start in Gas Station (O(n²)).