Jump Game Problem in DSA C++ - Execution Trace

Concept Flow - Jump Game Problem

Start at index 0

↓

Check if current index is last?

Yes→Return True

No↓

From current index, find reachable next indices

↓

Choose next index to jump

↓

Move to next index

↓

Repeat until last index reached or no moves left

↓

If no moves left and last not reached

→Return False

Start from the first position, check if you can reach the last by jumping within allowed steps, repeat until success or stuck.

Execution Sample

DSA C++

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

Check if you can jump through the array from start to end by tracking the farthest reachable index.

Execution Table

Step	Index i	nums[i]	maxReach before	Condition i > maxReach?	maxReach after	Action	Reachable Indices	Visual State
1	0	2	0	0 > 0? No	max(0, 0+2)=2	Update maxReach to 2	[1,2]	[0(2) -> 1 -> 2 -> ...]
2	1	3	2	1 > 2? No	max(2, 1+3)=4	Update maxReach to 4	[2,3,4]	[0 -> 1(3) -> 2 -> 3 -> 4 -> ...]
3	2	1	4	2 > 4? No	max(4, 2+1)=4	maxReach unchanged	[3,4]	[... 2(1) -> 3 -> 4 -> ...]
4	3	1	4	3 > 4? No	max(4, 3+1)=4	maxReach unchanged	[4]	[... 3(1) -> 4 -> ...]
5	4	0	4	4 > 4? No	max(4, 4+0)=4	maxReach unchanged	[]	[... 4(0) end]

💡 Loop ends after index 4, maxReach covers last index, so return True

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
i	0	1	2	3	4	End	4
maxReach	0	2	4	4	4	4	4

Key Moments - 3 Insights

Why do we check if i > maxReach before updating maxReach?

Because if current index i is beyond maxReach, it means we cannot jump to i, so we must stop and return false. See execution_table step 3 condition check.

Why does maxReach sometimes stay the same after an iteration?

If the current jump doesn't extend the farthest reachable index, maxReach remains unchanged. For example, at step 3 and 4, maxReach stays 4 as i + nums[i] is not greater.

How do we know when to return true?

If we finish the loop without returning false, it means maxReach covers or passes the last index. The exit_note confirms this after step 5.

Visual Quiz - 3 Questions

Look at the execution_table, what is maxReach after step 2?

A 2

B 3

C 4

D 1

💡 Hint

Check the 'maxReach after' column in row for step 2.

At which step does the condition i > maxReach become true causing early termination?

A Step 3

B Never in this example

C Step 5

D Step 1

💡 Hint

Look at the 'Condition i > maxReach?' column for all steps.

If nums[1] was 1 instead of 3, what would maxReach be after step 2?

A 2

B 3

C 1

D 4

💡 Hint

Calculate maxReach = max(previous maxReach, i + nums[i]) at step 2 with nums[1]=1.

Concept Snapshot

Jump Game Problem:
- Start at index 0
- Track maxReach: farthest index reachable
- For each index i:
  - If i > maxReach, return false
  - Update maxReach = max(maxReach, i + nums[i])
- If loop ends, return true (last index reachable)

Full Transcript

The Jump Game problem asks if you can reach the last index of an array starting from the first index. Each element tells you the maximum jump length from that position. We track the farthest reachable index called maxReach. Starting from index 0, for each index i, if i is beyond maxReach, it means we cannot reach i, so we return false. Otherwise, we update maxReach to the maximum of current maxReach and i plus nums[i]. If we finish checking all indices without failing, it means the last index is reachable, so we return true. The execution table shows step-by-step how maxReach changes and how the condition is checked. Key moments include understanding why we check i > maxReach and when to return true or false.

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