Jump Game Problem in DSA Javascript - Time & Space Complexity

Time Complexity: Jump Game Problem

O(n)

Understanding Time Complexity

We want to understand how the time needed to solve the Jump Game problem changes as the input array grows.

Specifically, how does the number of steps to check jumps grow with the size of the array?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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;
}
    

This code checks if you can jump from the start to the end of the array, where each number tells the max jump length from that position.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop that goes through the array once.
• How many times: Exactly once for each element in the array.

How Execution Grows With Input

As the array size grows, the number of steps grows directly with it.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The work grows in a straight line with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to decide if you can jump to the end grows linearly with the number of positions.

Common Mistake

[X] Wrong: "Because we check jumps from each position, the time is quadratic O(n²)."

[OK] Correct: The code only loops once through the array and updates the farthest reachable index without nested loops, so it does not multiply the work.

Interview Connect

Understanding this linear time solution shows you can optimize problems by avoiding unnecessary repeated checks, a key skill in interviews.

Self-Check

"What if the code used nested loops to check all possible jumps from each position? How would the time complexity change?"

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