Jump Game (Can Reach End?)

▶

Steps

setup

Initialize maxReach to 0

We start by setting maxReach to 0, meaning initially we can only reach the first index.

💡 This initialization sets the baseline for how far we can jump from the start.

Line:

maxReach = 0

💡 maxReach tracks the farthest index reachable so far.

traverse

Start iteration at index 0

Set i to 0, the first index, to begin checking jumps from the start.

💡 We examine each index to see if it is reachable and update maxReach accordingly.

Line:

for i, jump in enumerate(nums):

💡 The iteration pointer i moves through the array to evaluate each position.

compare

Check if current index 0 is reachable

Compare i (0) with maxReach (0). Since i <= maxReach, we can proceed.

💡 If i was greater than maxReach, it would mean we are stuck and cannot move forward.

Line:

if i > maxReach:
    return False

💡 Current index is reachable, so we continue updating maxReach.

expand

Update maxReach from index 0

Calculate new reach: i + nums[i] = 0 + 2 = 2. Update maxReach to max(0, 2) = 2.

💡 Updating maxReach shows how far we can jump from the current position.

Line:

maxReach = max(maxReach, i + jump)

💡 maxReach now reflects the farthest reachable index after considering jumps from index 0.

compare

Check if maxReach reaches or exceeds last index

maxReach (2) is less than last index (4), so continue iterating.

💡 We only stop early if maxReach reaches or passes the last index.

Line:

if maxReach >= len(nums) - 1:
    return True

💡 The end is not yet reachable, so we keep checking further indices.

traverse

Move to index 1

Increment i to 1 to evaluate jumps from the second element.

💡 We check each index in order to update maxReach if possible.

Line:

for i, jump in enumerate(nums):

💡 The iteration pointer moves forward to explore new jump possibilities.

compare

Check if current index 1 is reachable

Compare i (1) with maxReach (2). Since i <= maxReach, continue.

💡 If i was greater than maxReach, we would be stuck and return false.

Line:

if i > maxReach:
    return False

💡 Index 1 is reachable, so we can update maxReach from here.

expand

Update maxReach from index 1

Calculate new reach: 1 + nums[1] = 1 + 3 = 4. Update maxReach to max(2, 4) = 4.

💡 This update shows that from index 1, we can jump directly to the last index.

Line:

maxReach = max(maxReach, i + jump)

💡 maxReach now covers the last index, meaning the end is reachable.

compare

Check if maxReach reaches or exceeds last index

maxReach (4) is equal to last index (4), so we can return true immediately.

💡 Once maxReach covers the last index, the end is reachable and we can stop.

Line:

if maxReach >= len(nums) - 1:
    return True

💡 The algorithm detects success early without checking remaining indices.

prune

Return true - end is reachable

Since maxReach covers the last index, the function returns true indicating the end is reachable.

💡 This final step confirms the algorithm's conclusion based on maxReach.

Line:

return True

💡 The algorithm successfully determines reachability without full traversal.

def canJump(nums):
    maxReach = 0  # STEP 1
    for i, jump in enumerate(nums):  # STEP 2, 6
        if i > maxReach:  # STEP 3, 7
            return False
        maxReach = max(maxReach, i + jump)  # STEP 4, 8
        if maxReach >= len(nums) - 1:  # STEP 5, 9
            return True  # STEP 10
    return False

📊

Jump Game (Can Reach End?) - Watch the Algorithm Execute, Step by Step

Watching the algorithm step through the array and update its maximum reach helps you understand why it can quickly determine if the end is reachable without exploring all paths.

setup

maxReach

2

0

3

1

1

2

1

3

4

4

Result: 0

traverse

maxReach

2

0

3

1

1

2

1

3

4

4

Result: 0

compare

maxReach

2

0

3

1

1

2

1

3

4

4

Result: 0

expand

i

2

0

3

1

maxReach

1

2

1

3

4

4

Result: 2

compare

i

2

0

3

1

maxReach

1

2

1

3

4

4

Result: 2

traverse

2

0

i

3

1

maxReach

1

2

1

3

4

4

Result: 2

compare

2

0

i

3

1

maxReach

1

2

1

3

4

4

Result: 2

expand

2

0

i

3

1

1

2

1

3

maxReach

4

4

Result: 4

compare

2

0

i

3

1

1

2

1

3

maxReach

4

4

Result: 4

prune

2

0

3

1

1

2

1

3

maxReach

4

4

Result: true

Key Takeaways

✓ Tracking the maximum reachable index (maxReach) allows the algorithm to decide reachability efficiently.

This insight is hard to see from code alone because the variable maxReach abstracts the jump logic into a single number.

✓ If the current index exceeds maxReach, the algorithm knows it is stuck and can return false immediately.

Visualizing this condition helps understand why the algorithm can prune exploration early.

✓ When maxReach reaches or passes the last index, the algorithm returns true without checking remaining indices.

Seeing this early termination in the trace clarifies the greedy approach's efficiency.

Practice

1. Identify the bug in the following code snippet for the Minimum Domino Rotations problem:

def minDominoRotations(A, B):
    def check(x):
        rotations_a = rotations_b = 0
        for i in range(len(A)):
            if A[i] != x and B[i] != x:
                return 0  # Bug here
            elif A[i] != x:
                rotations_a += 1
            elif B[i] != x:
                rotations_b += 1
        return min(rotations_a, rotations_b)

    rotations = check(A[0])
    if rotations != -1:
        return rotations
    else:
        return check(B[0])

medium

A. Incorrect initialization of rotations_a and rotations_b

B. Not incrementing rotations when both sides equal x

C. Returning rotations without checking both candidates

D. The return value 0 instead of -1 when no domino can be rotated to x

Solution

1. Step 1: Analyze early return condition

   If neither side matches candidate x, the function should return -1 to indicate failure, not 0.

2. Step 2: Impact of returning 0

   Returning 0 falsely indicates zero rotations needed, causing incorrect positive results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Returning -1 signals no solution; 0 misleads caller [OK]

Hint: Return -1 on failure, not 0 [OK]

Common Mistakes:

• Returning 0 instead of -1 on failure
• Overcounting rotations when both sides equal candidate

2. What is the time complexity of the optimal greedy algorithm using a stack to remove k digits from a number string of length n to get the smallest number?

medium

A. O(n) because each digit is pushed and popped at most once

B. O(n^2) because nested loops are needed to find digits to remove

C. O(n log n) due to sorting digits internally

D. O(n * k) because each digit can cause up to k pops

Solution

1. Step 1: Identify operations per digit

   Each digit is pushed onto the stack once and can be popped at most once when a smaller digit arrives.

2. Step 2: Analyze total operations

   Since each push and pop happens at most once per digit, total operations are proportional to n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Stack operations are linear in n, no nested loops [OK]

Hint: Each digit pushed/popped once -> O(n) time [OK]

Common Mistakes:

• Assuming worst case k pops per digit -> O(n*k)
• Confusing with sorting complexity
• Thinking nested loops are needed

3. Suppose the problem changes: you can reuse indices multiple times (cycles allowed). Which modification to the BFS approach ensures correct minimum jumps without infinite loops?

hard

A. Remove the visited set to allow revisiting indices for better paths.

B. Keep the visited set but reset it after each BFS level to allow revisits in next level.

C. Keep the visited set as is to prevent revisiting and infinite loops.

D. Use a distance array to track minimum jumps to each index and update it if a shorter path is found.

Solution

1. Step 1: Understand cycles and revisits

   Allowing reuse means indices can be revisited, so visited set alone blocks better paths.

2. Step 2: Use distance array for shortest paths

   Tracking minimum jumps per index and updating when a shorter path is found prevents infinite loops and finds optimal jumps.

3. Step 3: Why other options fail

   Removing visited causes infinite loops; resetting visited loses pruning; keeping visited blocks revisits.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Distance array with updates handles cycles correctly [OK]

Hint: Distance array needed when revisits allowed [OK]

Common Mistakes:

• Removing visited set causing infinite loops
• Resetting visited incorrectly
• Assuming original BFS works unchanged

4. Suppose the problem is modified: instead of finding the largest monotone increasing digits number ≤ n, you want the largest monotone increasing digits number ≤ n that can reuse digits any number of times (digits can be repeated arbitrarily). Which approach correctly adapts the algorithm?

hard

A. Use the original greedy algorithm but allow digits after marker to be any digit less than or equal to the digit at marker-1

B. Sort the digits of n and build the largest monotone number by repeating the smallest digit as many times as needed

C. Use a backtracking approach to generate all monotone numbers with digits ≤ those in n, allowing reuse, and pick the largest ≤ n

D. Modify the greedy algorithm to decrement digits and set trailing digits to the digit at marker-1 instead of 9

Solution

1. Step 1: Understand digit reuse changes problem nature

   Allowing reuse means digits can be repeated arbitrarily, so greedy digit decrement and trailing 9 assignment no longer guarantee largest monotone number ≤ n.

2. Step 2: Backtracking enumerates all monotone numbers with digit reuse

   Backtracking can generate all monotone numbers with digits ≤ those in n, allowing reuse, then pick the largest ≤ n.

3. Step 3: Other options fail to handle reuse or produce incorrect numbers

   Sorting digits or modifying trailing digits to marker-1 digit does not guarantee largest monotone number with reuse.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Backtracking correctly handles reuse and monotonicity constraints [OK]

Hint: Digit reuse breaks greedy; backtracking needed for correctness [OK]

Common Mistakes:

• Trying to adapt greedy without full enumeration
• Assuming trailing digits can be set to 9 or marker digit
• Ignoring exponential complexity of reuse

5. Suppose the problem is modified so that characters can be reused unlimited times (infinite supply), and you want to generate a string of length n with no two adjacent characters the same. Which modification to the max heap approach is necessary to handle this variant correctly?

hard

A. No change needed; the original heap approach works as is for infinite reuse

B. Track only the last used character and pick any other character from the set for the next position

C. Use a queue instead of a heap to cycle through characters ensuring no adjacency

D. Remove frequency counts and always push characters back immediately after use to allow reuse

Solution

1. Step 1: Understand infinite reuse implication

   Since characters can be reused infinitely, frequency counts are irrelevant; characters must be available again immediately after use.

2. Step 2: Modify heap usage

   Remove frequency decrement logic and always push characters back immediately after use to allow reuse while avoiding adjacency.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Immediate pushback enables infinite reuse without adjacency violation [OK]

Hint: Infinite reuse means no frequency decrement [OK]

Common Mistakes:

• Assuming original approach works unchanged
• Using queue without frequency logic
• Ignoring adjacency constraints