Jump Game Problem in DSA Javascript - Execution Trace

Concept Flow - Jump Game Problem

Start at index 0

↓

Check if current index can reach end

↓

From current index, jump to reachable indices

↓

Mark reachable indices as visited

↓

If end index is reached -> Success

↓

If no new reachable indices -> Fail

Start from the first position, jump to all reachable positions, mark them visited, and check if the last index can be reached.

Execution Sample

DSA Javascript

const canJump = (nums) => {
  let maxReach = 0;
  for (let i = 0; i <= maxReach; i++) {
    maxReach = Math.max(maxReach, i + nums[i]);
    if (maxReach >= nums.length - 1) return true;
  }
  return false;
};

This code checks if you can jump from the start to the end of the array by tracking the furthest reachable index.

Execution Table

Step	Index i	nums[i]	maxReach Before	maxReach After	Can Reach End?	Action	Visual State
1	0	2	0	2	No	Update maxReach to max(0, 0+2)=2	[0(2), 1, 2, 3, 4] maxReach=2
2	1	3	2	4	Yes	Update maxReach to max(2, 1+3)=4; maxReach >= 4, return true	[0(2), 1(3), 2, 3, 4] maxReach=4
Exit	-	-	-	-	Yes	Reached or passed last index, stop	[0(2), 1(3), 2, 3, 4] maxReach=4

💡 maxReach reached or passed last index (4), so we can reach the end.

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
i	0	1	2	Stopped
maxReach	0	2	4	4

Key Moments - 3 Insights

Why do we stop the loop when i > maxReach?

Because if i is greater than maxReach, it means we cannot jump to index i, so no further progress is possible. This is shown in the execution_table where the loop only runs while i <= maxReach.

Why do we update maxReach with Math.max(maxReach, i + nums[i])?

Because from index i, we can jump up to i + nums[i]. We keep track of the furthest reachable index to know how far we can go. This is shown in the execution_table where maxReach updates at each step.

What does it mean when maxReach >= nums.length - 1?

It means we can reach or pass the last index of the array, so the answer is true. This is the exit condition in the execution_table at step 2.

Visual Quiz - 3 Questions

Look at the execution_table at Step 1, what is the value of maxReach after updating?

A 2

B 1

C 0

D 3

💡 Hint

Check the 'maxReach After' column at Step 1 in the execution_table.

At which step does the algorithm decide it can reach the end?

A Step 1

B Step 3

C Step 2

D It never reaches the end

💡 Hint

Look at the 'Can Reach End?' column in the execution_table.

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

A 3

B 2

C 4

D 1

💡 Hint

Calculate maxReach as max(previous maxReach, i + nums[i]) at Step 2.

Concept Snapshot

Jump Game Problem:
- Given array nums, each element is max jump length.
- Track maxReach: furthest index reachable so far.
- Loop i from 0 to maxReach.
- Update maxReach = max(maxReach, i + nums[i]).
- If maxReach >= last index, return true.
- Else, return false if loop ends.

Full Transcript

The Jump Game problem asks if you can jump from the start to the end of an array where each element tells you the maximum jump length from that position. We start at index 0 and keep track of the furthest index we can reach, called maxReach. We loop through the array indices up to maxReach. At each index i, we update maxReach to the maximum of its current value and i plus nums[i]. If at any point maxReach reaches or passes the last index, we return true, meaning we can reach the end. If the loop finishes without reaching the end, we return false. The execution table shows how maxReach changes step by step and when the algorithm stops. Key points include stopping the loop when i exceeds maxReach because we cannot jump further, and updating maxReach to track the furthest reachable position.

Practice

1. What does the Jump Game problem ask you to determine given an array of non-negative integers?

easy

A. If you can reach the last index starting from the first index

B. The maximum jump length from any position

C. The minimum number of jumps to reach the last index

D. The sum of all jump lengths in the array

Solution

1. Step 1: Understand the problem statement

   The Jump Game problem asks if it is possible to move from the first index to the last index by jumping according to the values in the array.

2. Step 2: Identify the goal

   The goal is to check if the last index is reachable, not the number of jumps or maximum jump length.

3. Final Answer:

   If you can reach the last index starting from the first index -> Option A

4. Quick Check:

   Jump Game = Reach last index [OK]

Hint: Focus on reachability, not jump counts or sums [OK]

Common Mistakes:

• Confusing reachability with minimum jumps
• Thinking about maximum jump length only
• Assuming sum of jumps matters

2. Which of the following is the correct syntax to check if you can jump from index i to index j in JavaScript, given an array nums?

easy

A. if (nums[i] >= j - i)

B. if (nums[j] <= i + nums[i])

C. if (j < nums[i])

D. if (j <= i + nums[i])

Solution

1. Step 1: Understand jump condition

   You can jump from index i to j if j is within the jump length from i, i.e., j ≤ i + nums[i].

2. Step 2: Match condition with options

   if (j <= i + nums[i]) correctly checks if j ≤ i + nums[i]. Other options compare wrong values or use incorrect operators.

3. Final Answer:

   if (j <= i + nums[i]) -> Option D

4. Quick Check:

   Jump condition = j ≤ i + nums[i] [OK]

Hint: Check if target index ≤ current index + jump length [OK]

Common Mistakes:

• Comparing nums[j] instead of j
• Using < instead of ≤
• Mixing indices and values incorrectly

3. What will be the output of the following JavaScript code?

function canJump(nums) {
  let maxReach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false;
    maxReach = Math.max(maxReach, i + nums[i]);
  }
  return true;
}

console.log(canJump([2,3,1,1,4]));
console.log(canJump([3,2,1,0,4]));

medium

A. true false

B. true true

C. false true

D. false false

Solution

1. Step 1: Trace first input [2,3,1,1,4]

   maxReach updates as: i=0 maxReach=2, i=1 maxReach=4, i=2 maxReach=4, i=3 maxReach=4, i=4 maxReach=8. No i > maxReach, so returns true.

2. Step 2: Trace second input [3,2,1,0,4]

   maxReach updates: i=0 maxReach=3, i=1 maxReach=3, i=2 maxReach=3, i=3 maxReach=3, i=4 i=4 > maxReach=3 triggers return false.

3. Final Answer:

   true false -> Option A

4. Quick Check:

   First array reachable, second not [OK]

Hint: Track max reachable index; fail if current index exceeds it [OK]

Common Mistakes:

• Not updating maxReach correctly
• Returning true too early
• Ignoring the condition i > maxReach

4. Identify the bug in the following code that attempts to solve the Jump Game problem:

function canJump(nums) {
  let maxReach = 0;
  for (let i = 0; i <= nums.length; i++) {
    if (i > maxReach) return false;
    maxReach = Math.max(maxReach, i + nums[i]);
  }
  return true;
}

medium

A. maxReach should be initialized to 1, not 0

B. The loop condition should be i < nums.length, not i <= nums.length

C. The return true statement should be inside the loop

D. The comparison should be i >= maxReach instead of i > maxReach

Solution

1. Step 1: Analyze loop boundary

   The loop runs from i = 0 to i <= nums.length, which means it accesses nums[nums.length], causing undefined access.

2. Step 2: Correct loop condition

   The loop should run while i < nums.length to avoid out-of-bounds errors.

3. Final Answer:

   The loop condition should be i < nums.length, not i <= nums.length -> Option B

4. Quick Check:

   Loop boundary off by one error [OK]

Hint: Check array indices carefully to avoid out-of-bounds [OK]

Common Mistakes:

• Using <= instead of < in loops
• Misinitializing maxReach
• Placing return true inside loop

5. Given the array nums = [1,2,0,1,0,2,0], which of the following statements is true about reaching the last index using the Jump Game logic?

hard

A. You can reach the last index only if you jump exactly 2 steps each time

B. You can reach the last index because jumps can skip zeros if reachable

C. You cannot reach the last index because zeros block all paths

D. You can reach the last index only if you jump backward at some point

Solution

1. Step 1: Trace maxReach for [1,2,0,1,0,2,0]

   i=0, maxReach=1; i=1, maxReach=3; i=2, maxReach=3; i=3, maxReach=4; i=4, maxReach=4; i=5 >4, cannot reach index 6.

2. Step 2: Analyze blocking

   Zeros at indices 2,4 limit jumps from reachable positions (max=4), blocking paths to end.

3. Final Answer:

   You cannot reach the last index because zeros block all paths -> Option C

4. Quick Check:

   Max reach=4 < length-1=6 [OK]

Hint: Trace maxReach step-by-step; zeros block if they stall reach before end [OK]

Common Mistakes:

• Thinking zeros can always be skipped sufficiently
• Assuming jumps must be fixed length
• Believing backward jumps are allowed