Jump Game - Practice Coding Problems

Jump Game - Problem

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Input & Output

Example 1 — Basic Case

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

› Output: true

💡 Note: Jump 1 step from index 0 to 1, then 3 steps to the last index. Or jump 2 steps from index 0 to 2, then 1 step to index 3, then 1 step to the last index.

Example 2 — Impossible Case

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

› Output: false

💡 Note: You will always arrive at index 3. Its maximum jump length is 0, so you cannot proceed further to reach the last index.

Example 3 — Single Element

$ Input: nums = [0]

› Output: true

💡 Note: Already at the last index, no jumping needed.

Constraints

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array where each element is max jump length

Process

Track farthest position reachable

Output

True if last index is reachable, false otherwise

Key Takeaway

🎯 Key Insight: Track the maximum reachable position greedily in one pass

Asked in

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

The greedy approach is optimal: track the maximum reachable position while iterating. If current position exceeds max reachable, return false. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Bottom-Up Dynamic Programming	O(n²)	O(n)	Build solution iteratively from the end to the beginning
Top-Down Dynamic Programming	O(n²)	O(n)	Cache recursive results to avoid redundant calculations
Greedy Algorithm	O(n)	O(1)	Track the farthest position reachable so far
Recursive Backtracking	O(2ⁿ)	O(n)	Try all possible jump combinations recursively

Bottom-Up Dynamic Programming — Algorithm Steps

Start from the last index (always good)
For each position, check if any jump leads to a good position
Mark current position as good if any jump succeeds

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Mark last position as good

Iterate

Work backwards, mark positions that can reach good positions

Result

Check if first position is good

Code -

solution.c — C

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

bool solution(int* nums, int numsSize) {
    bool* dp = (bool*)calloc(numsSize, sizeof(bool));
    dp[numsSize - 1] = true; // Last position is always reachable
    
    for (int i = numsSize - 2; i >= 0; i--) {
        int furthest = i + nums[i];
        if (furthest > numsSize - 1) {
            furthest = numsSize - 1;
        }
        
        for (int j = i + 1; j <= furthest; j++) {
            if (dp[j]) {
                dp[i] = true;
                break;
            }
        }
    }
    
    bool result = dp[0];
    free(dp);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    bool result = solution(nums, numsSize);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Two nested loops: outer loop iterates n positions, inner loop can check up to n jumps

⚠ Quadratic Growth

Space Complexity

O(n)

DP array stores the state (good/bad) for each position

⚡ Linearithmic Space

78.0K Views

High Frequency

~15 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

Bottom-Up Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler