Jump Game Problem in DSA Typescript - Execution Trace

Concept Flow - Jump Game Problem

Start at index 0

↓

Check max jump from current index

↓

Update furthest reachable index

↓

Move to next index

↓

Is current index <= furthest reachable?

↓

Return False

↓

Reached last index?

↓

Return True

Start from the first position, check how far you can jump, update the furthest reachable index, move forward, and verify if you can reach the end.

Execution Sample

DSA Typescript

function canJump(nums: number[]): boolean {
  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 by tracking the furthest reachable index.

Execution Table

Step	Operation	Current Index (i)	nums[i]	Max Reach Before	Max Reach After	Condition i <= Max Reach	Action	Visual State
1	Start loop	0	2	0	2	0 <= 0 (True)	Update maxReach to 2	maxReach=2; i=0
2	Next iteration	1	3	2	4	1 <= 2 (True)	Update maxReach to 4	maxReach=4; i=1
3	Next iteration	2	1	4	4	2 <= 4 (True)	maxReach stays 4	maxReach=4; i=2
4	Next iteration	3	1	4	4	3 <= 4 (True)	maxReach stays 4	maxReach=4; i=3
5	Next iteration	4	0	4	4	4 <= 4 (True)	maxReach stays 4	maxReach=4; i=4
6	Loop ends	-	-	-	-	-	Reached end, return True	Final maxReach=4, length=5

💡 Loop ends after i reaches last index; maxReach >= 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	0	1	2	3	4	5 (loop ends)
maxReach	0	2	4	4	4	4	4

Key Moments - 3 Insights

Why do we check if current index i is greater than maxReach?

Because if i > maxReach, it means we cannot reach position i from any previous jumps, so we must stop and return false. See execution_table row 3 where condition is checked.

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

Because from position i, we can jump up to nums[i] steps, so i + nums[i] is the furthest reachable index from i. We keep the maximum to know how far we can go overall. See execution_table rows 1 and 2 for updates.

What happens if maxReach never reaches the last index?

The loop will eventually find an index i that is greater than maxReach, causing the function to return false early. This is shown in the condition check in execution_table.

Visual Quiz - 3 Questions

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

A 4

B 3

C 2

D 1

💡 Hint

Check the 'Max Reach After' column at Step 2 in execution_table

At which step does the condition i <= maxReach become false causing the function to return false?

A Step 3

B Step 6

C It never becomes false in this example

D Step 1

💡 Hint

Look at the 'Condition i <= Max Reach' column for all steps in execution_table

If nums[1] was 0 instead of 3, what would happen to maxReach at Step 2?

A maxReach would become 1

B maxReach would stay 2

C maxReach would become 3

D maxReach would become 0

💡 Hint

Consider maxReach = Math.max(previous maxReach, i + nums[i]) with nums[1] = 0

Concept Snapshot

Jump Game Problem:
- Start at index 0
- Track maxReach = furthest index reachable
- For each index i:
  - If i > maxReach, return false
  - Update maxReach = max(maxReach, i + nums[i])
- If loop ends, return true
- Checks if end is reachable by jumps

Full Transcript

The Jump Game problem asks if you can reach the last index of an array starting from the first index. Each element in the array represents the maximum jump length from that position. The solution tracks the furthest reachable index as it iterates through the array. If at any point the current index is beyond the furthest reachable index, it means you cannot proceed further and the function returns false. Otherwise, if the loop completes, it means the last index is reachable and returns true. The execution table shows step-by-step how maxReach updates and how the condition is checked at each index.

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 by jumping according to the values.

B. The maximum jump length you can make from any position in the array.

C. The minimum number of jumps needed 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 you can start at the first index and reach the last index by jumping forward using the numbers in the array as maximum jump lengths.

2. Step 2: Identify the key goal

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

3. Final Answer:

   If you can reach the last index starting from the first index by jumping according to the values. -> 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 needed
• Thinking the problem asks for maximum jump length
• Assuming sum of jumps is the answer

2. Which of the following TypeScript function signatures correctly represents a function solving the Jump Game problem?

easy

A. function canJump(nums: number[]): boolean

B. function canJump(nums: number): number[]

C. function canJump(nums: string[]): boolean

D. function canJump(nums: number[][]): boolean

Solution

1. Step 1: Analyze the input and output types

   The input is an array of numbers representing jump lengths, so type is number[]. The output is a boolean indicating if last index is reachable.

2. Step 2: Match the function signature

   function canJump(nums: number[]): boolean matches input type number[] and output boolean, which fits the problem.

3. Final Answer:

   function canJump(nums: number[]): boolean -> Option A

4. Quick Check:

   Input array, output boolean = function canJump(nums: number[]): boolean [OK]

Hint: Input array of numbers, output boolean for reachability [OK]

Common Mistakes:

• Using wrong input types like string or 2D arrays
• Returning array instead of boolean
• Incorrect function parameter types

3. What is the output of the following TypeScript code?

function canJump(nums: number[]): boolean {
  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]));

medium

A. Runtime error

B. false

C. undefined

D. true

Solution

1. Step 1: Trace the loop and maxReach updates

   Start maxReach=0. i=0: maxReach=max(0,0+2)=2; i=1: 1<=2, maxReach=max(2,1+3)=4; i=2: 2<=4, maxReach=max(4,2+1)=4; i=3: 3<=4, maxReach=max(4,3+1)=4; i=4: 4<=4, maxReach=max(4,4+4)=8.

2. Step 2: Check if loop completes without returning false

   Since i never exceeds maxReach, loop completes and returns true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   All indices reachable, so true [OK]

Hint: Check if current index exceeds max reachable index [OK]

Common Mistakes:

• Not updating maxReach correctly
• Returning false too early
• Confusing output with minimum jumps

4. Identify the bug in this TypeScript code for the Jump Game problem:

function canJump(nums: number[]): boolean {
  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. The return type should be number, not boolean.

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

C. maxReach should be initialized to 1 instead of 0.

D. The function should return false at the end instead of true.

Solution

1. Step 1: Check loop boundary conditions

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

2. Step 2: Correct the loop condition

   Changing to i < nums.length prevents out-of-bounds access and fixes the bug.

3. Final Answer:

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

4. Quick Check:

   Loop index must stay within array bounds [OK]

Hint: Loop index must be less than array length [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Ignoring out-of-bounds array access
• Incorrect initialization of maxReach

5. Given the array [3,2,1,0,4], why does the standard greedy Jump Game algorithm return false?

hard

A. Because the array length is less than 5, so it always returns false.

B. Because the maximum jump length at index 0 is too large.

C. Because the zero at index 3 blocks any further jumps, making the last index unreachable.

D. Because the algorithm only checks the first two elements.

Solution

1. Step 1: Analyze jump reachability step-by-step

   Start maxReach=0. i=0: maxReach=max(0,0+3)=3; i=1: 1<=3, maxReach=max(3,1+2)=3; i=2: 2<=3, maxReach=max(3,2+1)=3; i=3: 3<=3, maxReach=max(3,3+0)=3; i=4: 4>3, return false.

2. Step 2: Understand why last index is unreachable

   The zero at index 3 prevents extending maxReach beyond 3, so index 4 cannot be reached.

3. Final Answer:

   Because the zero at index 3 blocks any further jumps, making the last index unreachable. -> Option C

4. Quick Check:

   Zero jump blocks progress = false [OK]

Hint: Zeros can block progress if maxReach can't pass them [OK]

Common Mistakes:

• Ignoring zeros that block jumps
• Assuming array length affects result
• Misunderstanding maxReach updates