Jump Game: When Greedy Replaces the DP Table

"Jump Game" is a Medium-level staple in Amazon, Microsoft, Meta loops, and it is a textbook fit for the Dynamic Programming pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 4 of 11 in the Dynamic Programming arc.

The Problem

Each position holds a maximum jump length; starting at index 0, can you reach the last index? Nominally a DP question — and the interview's real test is recognizing that the DP collapses to a single running maximum.

Input:  nums = [2, 3, 1, 1, 4]
Output: True
[3, 2, 1, 0, 4] is False — index 3 is a wall.

Recognizing the Dynamic Programming Pattern

Dynamic programming is recursion with the repetition removed: define the answer to a subproblem, express it in terms of smaller subproblems, and compute each exactly once — top-down with memoization or bottom-up with a table. In interviews the grade hinges on the state definition said out loud ('dp[i] is the best answer using the first i items') far more than on the loop that follows. Most FAANG DP questions are one-dimensional or a small 2D grid — the nine below cover the shapes that repeat.

Reachability is monotone — reaching index i means reaching everything before it — so the full reachable set compresses to its frontier: one integer, the farthest reachable index. When a DP state is monotone, look for the collapse; this question exists to reward that look.

The Approach

Sweep left to right maintaining farthest. If the current index exceeds farthest, you are stranded — False. Otherwise extend with i + nums[i]; early True once the last index is within reach.

Present the O(n²) DP (each cell reachable if some reachable predecessor jumps to it) in one sentence as the baseline, then collapse it — showing the compression is the senior answer, and it sets up Jump Game II's interval-BFS greedy naturally.

Python Solution

def can_jump(nums: list[int]) -> bool:
    """True if the last index is reachable from index 0."""
    farthest = 0
    last = len(nums) - 1
    for i, jump in enumerate(nums):
        if i > farthest:
            return False               # stranded before reaching i
        farthest = max(farthest, i + jump)
        if farthest >= last:
            return True
    return True

Complexity

• Time: O(n) — one pass, constant work per index
• Space: O(1) — one frontier integer

Interview Tips and Follow-Ups

• Jump Game II (minimum jumps) is the follow-up nine times out of ten: greedy layers — current reach, next reach, count a jump when the layer ends. Rehearse it.
• Zeros are the danger cells; [1, 0, 1] fails while [2, 0, 0] passes — a pair worth quoting to show edge fluency.
• Say when greedy legitimately replaces DP (monotone state, verifiable frontier) — the meta-answer interviewers fish for with this problem.

If this clicked, continue the Dynamic Programming arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.