Jump Game Problem in DSA C++

Mental Model

You can jump forward from each position by a number of steps given by the value at that position. The goal is to see if you can reach the last position starting from the first.

Analogy: Imagine standing on stepping stones across a river. Each stone has a number telling you how many stones you can jump forward. You want to know if you can reach the last stone without falling in the water.

Index: 0   1   2   3   4
Value: [2] -> [3] -> [1] -> [1] -> [4]
Start ↑

Dry Run Walkthrough

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

Goal: Determine if you can jump from the first index to the last index following the jump rules.

Step 1: Start at index 0 with max reachable index = 0

Current index: 0, max reachable: 0

Why: We begin at the first stone and can jump up to 2 steps ahead.

Step 2: At index 0, update max reachable to max(0, 0 + 2) = 2

Current index: 0, max reachable: 2

Why: From stone 0, we can jump up to stone 2.

Step 3: Move to index 1 since 1 <= max reachable (2)

Current index: 1, max reachable: 2

Why: We can safely move to stone 1 because it is within reach.

Step 4: At index 1, update max reachable to max(2, 1 + 3) = 4

Current index: 1, max reachable: 4

Why: From stone 1, we can jump up to stone 4, which is the last stone.

Step 5: Since max reachable (4) >= last index (4), return true

Current index: 1, max reachable: 4

Why: We can reach or pass the last stone, so the answer is yes.

Result:

2 -> 3 -> 1 -> 1 -> 4
Can reach last index: true

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (i > maxReach) return false; // can't reach this position
            maxReach = max(maxReach, i + nums[i]); // update max reachable index
            if (maxReach >= (int)nums.size() - 1) return true; // can reach last index
        }
        return false;
    }
};

int main() {
    vector<int> nums = {2, 3, 1, 1, 4};
    Solution sol;
    bool result = sol.canJump(nums);
    for (int num : nums) cout << num << " -> ";
    cout << "null" << endl;
    cout << (result ? "Can reach last index: true" : "Can reach last index: false") << endl;
    return 0;
}

if (i > maxReach) return false; // can't reach this position

stop if current index is beyond max reachable index

maxReach = max(maxReach, i + nums[i]); // update max reachable index

update max reachable index based on current position and jump length

if (maxReach >= nums.size() - 1) return true; // can reach last index

return true immediately if last index is reachable

Output

2 -> 3 -> 1 -> 1 -> 4 -> null

Can reach last index: true

Complexity Analysis

Time: O(n) because we scan the list once, updating the farthest reachable index.

Space: O(1) because we use only a few variables regardless of input size.

vs Alternative: Compared to a recursive or backtracking approach that tries all jumps (exponential time), this greedy method is much faster and simpler.

Edge Cases

Empty array

Returns false because the loop does not execute.

DSA C++

for (int i = 0; i < nums.size(); ++i) {

Single element array [0]

Returns true because start is also the last index.

DSA C++

if (maxReach >= nums.size() - 1) return true;

Array with zero blocking progress [3,2,1,0,4]

Returns false because cannot jump past zero at index 3.

DSA C++

if (i > maxReach) return false;

When to Use This Pattern

When you see a problem asking if you can reach the end by jumping variable steps, use the greedy max reachable index pattern to efficiently check reachability.

Common Mistakes

Mistake: Trying to explore all jump paths recursively causing timeouts.
Fix: Use a greedy approach tracking the farthest reachable index to avoid unnecessary work.

Mistake: Not checking if current index is beyond max reachable, leading to incorrect true results.
Fix: Add a condition to return false immediately if current index is unreachable.

Summary

Determines if you can jump from start to end of an array using jump lengths at each position.

Use when you need to check reachability in a jump or step-based problem efficiently.

Keep track of the farthest reachable position and stop early if you can't progress.

Practice

1. What is the main goal of the Jump Game problem?

easy

A. Count the total number of jumps needed to reach the end

B. Find the maximum jump length from the first index

C. Calculate the minimum jump length required to reach the last index

D. Determine if you can reach the last index from the first index by jumping

Solution

1. Step 1: Understand the problem statement

   The Jump Game problem asks if it is possible to move from the first position of an array to the last position by jumping forward. Each array element represents the maximum jump length from that position.

2. Step 2: Identify the goal

   The goal is to check if the last index can be reached starting from the first index using the allowed jumps.

3. Final Answer:

   Determine if you can reach the last index from the first index by jumping -> Option D

4. Quick Check:

   Jump Game goal = Reach last index [OK]

Hint: Focus on reachability from start to end index [OK]

Common Mistakes:

• Confusing maximum jump length with total jumps
• Trying to count jumps instead of checking reachability
• Assuming jumps can be backward

2. Which of the following is the correct C++ syntax to declare a vector named nums initialized with values {2,3,1,1,4}?

easy

A. vector nums = [2,3,1,1,4];

B. std::vector nums = {2,3,1,1,4};

C. std::vector<int> nums = {2,3,1,1,4};

D. std::vector<int> nums(2,3,1,1,4);

Solution

1. Step 1: Understand vector declaration syntax

   In C++, to declare a vector of integers with initial values, use std::vector<int> nums = {values};.

2. Step 2: Check each option

   std::vector<int> nums = {2,3,1,1,4}; uses correct syntax with type and initializer list. Options A and C miss template type or use wrong brackets. std::vector<int> nums(2,3,1,1,4); uses constructor incorrectly.

3. Final Answer:

   std::vector<int> nums = {2,3,1,1,4}; -> Option C

4. Quick Check:

   Correct vector initialization syntax = std::vector<int> nums = {2,3,1,1,4}; [OK]

Hint: Use std::vector<int> with curly braces for initialization [OK]

Common Mistakes:

• Omitting <int> in vector declaration
• Using square brackets [] instead of curly braces {}
• Incorrect constructor parameters

3. What will be the output of the following C++ code snippet?

std::vector<int> nums = {2,3,1,1,4};
int maxReach = 0;
for (int i = 0; i <= maxReach; ++i) {
    maxReach = std::max(maxReach, i + nums[i]);
    if (maxReach >= nums.size() - 1) {
        std::cout << "true" << std::endl;
        break;
    }
}
if (maxReach < nums.size() - 1) std::cout << "false" << std::endl;

medium

A. false

B. true

C. Compilation error

D. Runtime error

Solution

1. Step 1: Trace the loop and maxReach updates

   Start with maxReach=0. At i=0, maxReach = max(0, 0+2) = 2. At i=1, maxReach = max(2, 1+3) = 4. Since maxReach (4) >= last index (4), print "true" and break.

2. Step 2: Confirm output

   The loop breaks after printing "true". No further output.

3. Final Answer:

   true -> Option B

4. Quick Check:

   maxReach reaches last index, output = true [OK]

Hint: Track maxReach and break when it reaches last index [OK]

Common Mistakes:

• Not updating maxReach correctly
• Missing break causing extra output
• Confusing index bounds in loop

4. Identify the error in the following C++ code for the Jump Game problem:

bool canJump(std::vector<int>& nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.size(); ++i) {
        if (i > maxReach) return false;
        maxReach = std::max(maxReach, i + nums[i]);
    }
    return true;
}

medium

A. No error, code works correctly

B. Return false should be after the loop, not inside

C. maxReach update is incorrect, should subtract 1

D. Loop condition should be i <= maxReach instead of i < nums.size()

Solution

1. Step 1: Analyze loop and conditions

   The loop iterates over all indices. If current index i is beyond maxReach, return false immediately. Otherwise, update maxReach.

2. Step 2: Verify correctness

   This logic correctly checks if the last index is reachable. Returning false inside loop is valid. maxReach update is correct.

3. Final Answer:

   No error, code works correctly -> Option A

4. Quick Check:

   Code logic matches Jump Game solution [OK]

Hint: Check if current index exceeds maxReach to return false early [OK]

Common Mistakes:

• Changing loop condition incorrectly
• Moving return false outside loop causing wrong result
• Incorrect maxReach calculation

5. Given the array nums = {3,2,1,0,4}, why does the standard greedy Jump Game algorithm return false?

hard

A. Because the zero at index 3 blocks any further jumps to the last index

B. Because the array length is less than 5

C. Because the first element is too large causing an overflow

D. Because the algorithm only works for arrays with all positive numbers

Solution

1. Step 1: Understand the array and jumps

   Starting at index 0 with jump length 3, you can reach indices 1, 2, or 3. At index 3, jump length is 0, so you cannot move forward from there.

2. Step 2: Identify why last index is unreachable

   Since index 4 is beyond index 3 and no jumps can be made from index 3, the last index cannot be reached, so the algorithm returns false.

3. Final Answer:

   Because the zero at index 3 blocks any further jumps to the last index -> Option A

4. Quick Check:

   Zero jump blocks path, output = false [OK]

Hint: Look for zero jump spots blocking progress [OK]

Common Mistakes:

• Ignoring zero jump blocking
• Assuming array length affects result
• Misunderstanding jump lengths