Jump Game Problem in DSA Typescript

Mental Model

You want to jump through an array from start to end using steps allowed by each position's number. The key is to check if you can reach the last position by jumping forward.

Analogy: Imagine stepping stones across a river. Each stone tells you how far you can jump next. You want to see if you can reach the last stone without falling in the water.

Start -> [3] -> 2 -> 1 -> 0 -> 4 -> End
Each number shows max jump length from that stone.

Dry Run Walkthrough

Input: array: [3, 2, 1, 0, 4]

Goal: Determine if you can jump from the first index to the last index following jump rules.

Step 1: Start at index 0 with jump length 3, max reachable index is 0 + 3 = 3

maxReach = 3, currentIndex = 0

Why: We can jump up to index 3 from start, so far so good.

Step 2: Move to index 1 with jump length 2, update maxReach to max(3, 1+2) = 3

maxReach = 3, currentIndex = 1

Why: From index 1, max jump is 3, no improvement.

Step 3: Move to index 2 with jump length 1, update maxReach to max(3, 2+1) = 3

maxReach = 3, currentIndex = 2

Why: From index 2, max jump is still 3, no improvement.

Step 4: Move to index 3 with jump length 0, maxReach stays 3

maxReach = 3, currentIndex = 3

Why: At index 3, jump length is 0, can't move forward from here.

Step 5: Try to move to index 4 but maxReach is 3, so index 4 is unreachable

maxReach = 3, currentIndex = 4 (unreachable)

Why: We cannot reach the last index because maxReach is less than 4.

Result:

Cannot reach last index: maxReach = 3 < lastIndex = 4

Annotated Code

DSA Typescript

class JumpGame {
  canJump(nums: number[]): boolean {
    let maxReach = 0;
    for (let i = 0; i < nums.length; i++) {
      if (i > maxReach) {
        return false; // can't reach this position
      }
      maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
  }
}

const game = new JumpGame();
const input = [3, 2, 1, 0, 4];
const result = game.canJump(input);
console.log(result ? "Can reach last index" : "Cannot reach last index");

if (i > maxReach) {

Check if current index is beyond max reachable index, if yes, return false

maxReach = Math.max(maxReach, i + nums[i]);

Update max reachable index based on current position and jump length

Output

Cannot reach last index

Complexity Analysis

Time: O(n) because we scan the array once updating max reachable index

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: Compared to recursive or backtracking approaches that try all paths (exponential), this greedy method is much faster and simpler.

Edge Cases

Empty array

Returns true because we are already at the last index

DSA Typescript

for (let i = 0; i < nums.length; i++) {

Single element array [0]

Returns true because start is the last index

DSA Typescript

for (let i = 0; i < nums.length; i++) {

Array with zero at start [0, 1]

Returns false because can't move anywhere

DSA Typescript

if (i > maxReach) {

When to Use This Pattern

When you see a problem asking if you can reach the end of an array by jumping steps defined at each position, use the greedy maxReach pattern to track how far you can go.

Common Mistakes

Mistake: Not checking if current index is beyond max reachable index before updating maxReach
Fix: Add a condition to return false immediately if current index is unreachable

Mistake: Trying to simulate all jump paths instead of tracking max reachable index
Fix: Use a single pass greedy approach updating maxReach to avoid exponential complexity

Summary

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

Use when you need to check reachability in jump or step-based array problems.

Keep track of the farthest index you can reach and fail early if stuck.