{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Jump Game – Solution & Complexity

Interview solutions
/
Jump Game

Solution Walkthrough

  1. Step 1: Understand Reachability

    • Each value tells you the maximum jump length from that index.
    • You only need to know whether the last index can be reached, not the exact path.
    • If you ever stand beyond the farthest reachable index, progress is impossible.

  2. Step 2: Brute Force or DP Idea

    • One approach marks which indices are reachable from earlier indices.
    • For every reachable index, mark all destinations within its jump range.
    • This can work, but it may take O(n²) time in large arrays.
    def can_jump(nums):
    reachable = [False] * len(nums)
    reachable[0] = True
    for i, jump in enumerate(nums):
        if reachable[i]:
            for nxt in range(i + 1, min(len(nums), i + jump + 1)):
                reachable[nxt] = True
    return reachable[-1]

  3. Step 3: Track the Farthest Reach

    • A greedy scan is enough because jumps only move forward.
    • Maintain farthest, the greatest index reachable so far.
    • At each reachable index, update farthest with i + nums[i].

  4. Step 4: Detect Failure or Success

    • If the current index is greater than farthest, there is no way to reach it, so return False.
    • If farthest reaches or passes the last index, return True.
    • Otherwise continue scanning reachable positions.
    def can_jump(nums):
    farthest = 0
    last = len(nums) - 1
    for i, jump in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + jump)
        if farthest >= last:
            return True
    return True

  5. Step 5: Final Complete Solution

    • The greedy invariant is that all indices up to farthest are reachable while scanning.
    • Time complexity is O(n) because each index is visited once.
    • Space complexity is O(1).
    def can_jump(nums: list[int]) -> bool:
    farthest = 0
    last = len(nums) - 1

    for i, jump in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + jump)
        if farthest >= last:
            return True

    return True

FAQ

See also

Practice Jump Game online (run code in the browser)Jump Game II solution (hard)Best Time to Buy and Sell Stock solution (easy)Coin Change solution (medium)Container With Most Water solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?