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.