Jump Game

Can you reach the end? Minimum jumps with greedy approach.

6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

Jump Game I - Can Reach End

Array nums where nums[i] = max jump length from i. Start at index 0. Determine if you can reach last index. Greedy: track furthest reachable index. If current index > furthest, stuck.

Gocan-reach-end.go

16 linesLn 1, Col 1Go

Single pass O(n). furthest = max index reachable so far. If we can't even reach current index, impossible. Update furthest with current jump capability.

Jump Game II - Minimum Jumps

Find minimum jumps to reach end. Greedy: track current jump's reach (currEnd) and next jump's furthest (currFarthest). When i reaches currEnd, must jump: increment count, extend currEnd to currFarthest.

Gominimum-jumps.go

21 linesLn 1, Col 1Go

Two pointers: currEnd marks where current jump's range ends. currFarthest tracks furthest we can reach in next jump. When we exhaust current range (i == currEnd), we commit to a jump.

Greedy Proof

For Jump II: any optimal solution must make a jump within the first range. Greedy chooses the position that extends reach furthest. Any other choice within first range reaches no further, so greedy is never worse. Inductive step applies to remaining subproblem.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.