Jump Game II - Practice Coding Problems

Jump Game II - Problem

You are given a 0-indexed array of integers nums of length n. You are initially positioned at index 0.

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at index i, you can jump to any index (i + j) where:

0 <= j <= nums[i] and i + j < n

Return the minimum number of jumps to reach index n - 1.

The test cases are generated such that you can reach index n - 1.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,3,1,1,4]

› Output: 2

💡 Note: Jump from index 0 to 1, then jump from index 1 to the last index. Total: 2 jumps.

Example 2 — Larger Jumps

$ Input: nums = [2,3,0,1,4]

› Output: 2

💡 Note: Jump from index 0 to 1 (or 2), then jump to index 4. Minimum is still 2 jumps.

Example 3 — Single Element

$ Input: nums = [1]

› Output: 0

💡 Note: Already at the last index, so 0 jumps needed.

Constraints

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 1000
It's guaranteed that you can reach nums[n - 1]

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array where each element shows max jump distance from that position

Find Path

Determine minimum number of jumps to reach the last index

Output

Return the minimum jump count

Key Takeaway

🎯 Key Insight: Use greedy strategy to jump to positions that maximize future reachability

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is to use a greedy approach that tracks the farthest reachable position at each step. Instead of trying all paths, we greedily choose jumps that maximize our future reach. The optimal greedy solution runs in O(n) time and O(1) space by maintaining current reach and farthest reach boundaries.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming	O(n²)	O(n)	Build up minimum jumps for each position
Greedy (Optimal)	O(n)	O(1)	Jump to the position that gives maximum future reach
Recursive Brute Force	O(2ⁿ)	O(n)	Try all possible jump paths recursively

Dynamic Programming — Algorithm Steps

Initialize DP array with infinity
Set dp[0] = 0 (start position)
For each position, check all positions that can jump to it
Take minimum jumps needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set dp[0] = 0, all others = ∞

Fill DP

For each position, find minimum jumps from reachable positions

Result

dp[n-1] contains minimum jumps to reach end

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int numsSize) {
    if (numsSize <= 1) return 0;
    
    int* dp = (int*)malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        dp[i] = INT_MAX;
    }
    dp[0] = 0;
    
    for (int i = 1; i < numsSize; i++) {
        for (int j = 0; j < i; j++) {
            if (j + nums[j] >= i && dp[j] != INT_MAX) {
                if (dp[j] + 1 < dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
    }
    
    int result = dp[numsSize - 1];
    free(dp);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops: for each position (n), check all previous positions that can reach it (up to n)

⚠ Quadratic Growth

Space Complexity

O(n)

DP array stores minimum jumps for each of the n positions

⚡ Linearithmic Space

65.0K Views

High Frequency

~25 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler