Jump Game

Free with account Updated Nov 19, 2026 · 4 min read
On this page

    Problem statement

    You start at index 0 of an array of non-negative integers. Each value is the longest jump you may take from that position (any shorter jump is also allowed). Return whether you can reach the last index.

    A short question with a one-variable greedy answer. Interviewers like it because the DP answer works too, and they want to hear why the greedy one is enough. Original problem: LeetCode 55.

    Example

    [2, 0, 3, 1, 0, 4] can jump 0 → 2 → 5. In [1, 2, 0, 0, 3], every route stops at index 3.
    [2, 0, 3, 1, 0, 4] can jump 0 → 2 → 5. In [1, 2, 0, 0, 3], every route stops at index 3.
    Input:  [2, 0, 3, 1, 0, 4]
    Output: true        # 0 → 2 → 5
    Input:  [1, 2, 0, 0, 3]
    Output: false       # farthest reachable index is 3
    Input:  [0]
    Output: true        # already at the last index

    Constraints (assumed)

    • 1 ≤ n ≤ 10⁴.
    • 0 ≤ value ≤ 10⁵.

    What this question tests

    • Seeing that the set of reachable indices is always a prefix 0..reach, so one number describes it.
    • Arguing why greedy is correct instead of guessing.
    • Knowing the O(n²) DP and why it isn't needed.

    Questions to ask first

    1. Is the value the exact jump length or the maximum? (Here: the maximum; shorter jumps are allowed.)
    2. Can values be negative? (Here: no.)
    3. Do you want yes/no, or the fewest jumps? The second is Jump Game II.
    4. Is a single-element array already at the end? (Yes.)