Jump Game Problem in DSA Javascript

Mental Model

You want to jump through an array from start to end using the numbers as max jump lengths. The question is if you can reach the last position.

Analogy: Imagine stepping stones across a river. Each stone lets you jump forward up to a certain number of stones. Can you 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: array: [2, 3, 1, 1, 4]

Goal: Determine if you can jump from the first index to the last index using the jump lengths given

Step 1: Start at index 0 with max jump 2, update farthest reachable to 2

Current index: 0, Farthest reachable index: 2

Why: We can jump up to 2 steps from the start

Step 2: Move to index 1 with jump 3, update farthest reachable to max(2, 1+3=4)

Current index: 1, Farthest reachable index: 4

Why: From index 1, we can jump farther, so update farthest reachable

Step 3: Move to index 2 with jump 1, farthest reachable remains 4

Current index: 2, Farthest reachable index: 4

Why: No farther jump than current farthest reachable

Step 4: Move to index 3 with jump 1, farthest reachable remains 4

Current index: 3, Farthest reachable index: 4

Why: Still can reach the end

Step 5: Since farthest reachable index 4 is last index, return true

Reached last index 4

Why: We can reach the last stone

Result:

True -- can reach last index

Annotated Code

DSA Javascript

class JumpGame {
  static canJump(nums) {
    let farthest = 0;
    for (let i = 0; i < nums.length; i++) {
      if (i > farthest) return false; // can't reach this index
      farthest = Math.max(farthest, i + nums[i]); // update farthest reachable
      if (farthest >= nums.length - 1) return true; // can reach or pass last index
    }
    return false;
  }
}

// Driver code
const nums = [2, 3, 1, 1, 4];
console.log(JumpGame.canJump(nums));

if (i > farthest) return false; // can't reach this index

stop if current index is beyond farthest reachable

farthest = Math.max(farthest, i + nums[i]); // update farthest reachable

update farthest reachable index from current position

if (farthest >= nums.length - 1) return true; // can reach or pass last index

return true if last index is reachable

Output

true

Complexity Analysis

Time: O(n) because we scan the array 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), this greedy method is much faster and uses less memory

Edge Cases

Empty array

Returns true because we are already at the last index

DSA Javascript

if (farthest >= nums.length - 1) return true;

Array with one element

Returns true because start is the last index

DSA Javascript

if (farthest >= nums.length - 1) return true;

Array where first element is 0 and length > 1

Returns false because can't move anywhere

DSA Javascript

if (i > farthest) return false;

When to Use This Pattern

When you see a problem asking if you can reach the end of an array by jumping variable steps, use the greedy farthest reachable index pattern to decide feasibility efficiently.

Common Mistakes

Mistake: Trying to simulate every jump path recursively causing timeouts
Fix: Use a greedy approach tracking the farthest reachable index instead of exploring all paths

Mistake: Not checking if current index is beyond farthest reachable, leading to incorrect true results
Fix: Add a condition to return false if current index is greater than farthest reachable

Summary

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

Use when you need to check reachability in jump or step problems efficiently.

Keep track of the farthest index you can reach and stop early if you can't progress.

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