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

Jump Game II – Solution & Complexity

Interview solutions
/
Jump Game II

Solution Walkthrough

  1. Step 1: Understanding the Problem

    • From index i you may jump to any index up to i + nums[i].
    • You always start at index 0 and are guaranteed to reach the end.
    • We want the fewest jumps to land on the last index.

  2. Step 2: Thinking in Levels (Implicit BFS)

    • Group indices by how many jumps it takes to first reach them.
    • Level 0 is just index 0; level 1 is everything reachable in one jump, and so on.
    • The answer is the level number of the last index — exactly a shortest-path / BFS idea, done greedily.

  3. Step 3: Tracking the Current Jump's Reach

    • end marks the farthest index covered by the current number of jumps.
    • farthest is the best index reachable while scanning the current level.
    • When i reaches end, we have exhausted this level and must take another jump.
    def jump(nums):
    jumps = 0
    start = 0
    end = 0
    while end < len(nums) - 1:
        farthest = end
        for i in range(start, end + 1):
            farthest = max(farthest, i + nums[i])
        jumps += 1
        start = end + 1
        end = farthest
    return jumps

  4. Step 4: The Greedy Scan

    • Iterate up to the second-to-last index (reaching it is enough).
    • Continuously extend farthest. When i == end, increment jumps and push end out to farthest.
    • This guarantees the minimum count because each jump greedily covers as far as possible.
    def jump(nums):
    jumps = 0
    end = 0
    farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == end:
            jumps += 1
            end = farthest
    return jumps

  5. Step 5: Complexity

    • Time: O(n) with a single pass over the array.
    • Space: O(1) extra.
    • A single element array needs 0 jumps, which the loop naturally returns.

FAQ

See also

Practice Jump Game II online (run code in the browser)Jump Game solution (medium)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?