Jump Game II (Minimum Jumps)

▶

Steps

setup

Initialize queue and visited set

Start by initializing the queue with the starting index 0 and mark it visited. Set jumps to 0.

💡 This sets up the BFS traversal starting from the first index, ensuring we don't revisit indices.

Line:

queue = deque([0])
visited = set([0])
jumps = 0

💡 The algorithm begins exploring from index 0 with zero jumps made so far.

traverse

Start first jump level

Begin processing the first level of BFS. The queue size is 1, and we increment jumps to 1.

💡 Incrementing jumps indicates we are exploring all positions reachable with one jump.

Line:

size = len(queue)
jumps += 1

💡 The first jump level includes only the starting index 0.

traverse

Dequeue position 0 to explore jumps

Dequeue index 0 from the queue to explore all reachable indices within jump length 2.

💡 We explore all indices reachable from 0 to find next positions to jump to.

Line:

pos = queue.popleft()

💡 Index 0 is the current position from which we try to jump forward.

compare

Calculate furthest jump from index 0

Calculate the furthest index reachable from position 0, which is min(0 + 2, 4) = 2.

💡 This determines the range of indices we can jump to from current position.

Line:

furthest_jump = min(pos + nums[pos], n - 1)

💡 We can jump to indices 1 and 2 from index 0.

insert

Enqueue index 1 as next position

Index 1 is within jump range and not visited, so add it to the queue and mark visited.

💡 Adding index 1 means we will explore jumps from there in the next BFS level.

Line:

if next_pos not in visited:
    visited.add(next_pos)
    queue.append(next_pos)

💡 Index 1 is now queued for exploration in the next jump level.

insert

Enqueue index 2 as next position

Index 2 is also reachable and unvisited, so add it to the queue and mark visited.

💡 We continue adding all reachable indices from current position to the queue.

Line:

if next_pos not in visited:
    visited.add(next_pos)
    queue.append(next_pos)

💡 Index 2 is now queued for exploration in the next jump level.

traverse

Finish processing first level, start second jump level

All positions reachable in one jump are enqueued. Now increment jumps to 2 for next level.

💡 Incrementing jumps means we are now exploring positions reachable in two jumps.

Line:

jumps += 1

💡 We move to the next BFS level representing the second jump.

traverse

Dequeue position 1 to explore jumps

Dequeue index 1 to explore reachable indices within jump length 3 from here.

💡 Exploring from index 1 may reach the last index directly.

Line:

pos = queue.popleft()

💡 Index 1 is the current position being expanded in the second jump level.

compare

Calculate furthest jump from index 1

Calculate furthest reachable index from 1: min(1 + 3, 4) = 4 (last index).

💡 This shows we can jump directly to the last index from here.

Line:

furthest_jump = min(pos + nums[pos], n - 1)

💡 The last index is reachable from index 1 in this jump.

compare

Reach last index and return jumps

Next position 4 is the last index, so return the current jump count 2 as the minimum jumps.

💡 Finding the last index means we have found the minimum jumps needed.

Line:

if next_pos == n - 1:
    return jumps

💡 The BFS level order traversal guarantees this is the minimum jump count.

from collections import deque

def jump(nums):
    n = len(nums)  # STEP 1
    if n == 1:
        return 0
    queue = deque([0])  # STEP 1
    visited = set([0])  # STEP 1
    jumps = 0  # STEP 1
    while queue:  # STEP 2
        size = len(queue)  # STEP 2
        jumps += 1  # STEP 2
        for _ in range(size):  # STEP 3
            pos = queue.popleft()  # STEP 3
            furthest_jump = min(pos + nums[pos], n - 1)  # STEP 4
            for next_pos in range(pos + 1, furthest_jump + 1):  # STEP 5-6
                if next_pos == n - 1:  # STEP 10
                    return jumps
                if next_pos not in visited:  # STEP 5-6
                    visited.add(next_pos)  # STEP 5-6
                    queue.append(next_pos)  # STEP 5-6
    return jumps

📊

Jump Game II (Minimum Jumps) - Watch the Algorithm Execute, Step by Step

Watching the queue expansion and jump increments visually reveals how the BFS level order traversal finds the minimum jumps efficiently.

setup

queue_front

2

0

3

1

1

2

1

3

4

4

Result: 0

move_left

queue_front

2

0

3

1

1

2

1

3

4

4

Result: 1

move_right

pos

2

0

3

1

1

2

1

3

4

4

Result: 1

compare

pos

2

0

3

1

furthest_jump

1

2

1

3

4

4

Result: 1

record

pos

2

0

next_pos

3

1

1

2

1

3

4

4

Result: 1

record

pos

2

0

3

1

next_pos

1

2

1

3

4

4

Result: 1

move_left

2

0

queue_front

3

1

1

2

1

3

4

4

Result: 2

move_right

2

0

pos

3

1

1

2

1

3

4

4

Result: 2

compare

2

0

pos

3

1

1

2

1

3

furthest_jump

4

4

Result: 2

compare

2

0

pos

3

1

1

2

1

3

next_pos

4

4

Result: 2

Key Takeaways

✓ The BFS level order traversal approach finds the minimum jumps by exploring all reachable indices level-by-level.

This insight is hard to see from code alone because the queue expansion and jump increments are implicit in loops.

✓ Incrementing the jump count after processing all nodes at the current level corresponds to making one more jump.

Visualizing jumps as BFS levels clarifies why the jump count increments only after exploring all positions reachable in the previous jump.

✓ The algorithm stops immediately when the last index is reached, ensuring the minimum jumps are returned.

Seeing the early return condition in the trace shows how the algorithm avoids unnecessary exploration.

Practice

1. Consider the following code snippet implementing the peak-valley approach to maximize stock profit. What is the final returned profit when the input prices are [1, 2, 3]?

def maxProfit(prices):
    i = 0
    profit = 0
    n = len(prices)
    while i < n - 1:
        while i < n - 1 and prices[i] >= prices[i + 1]:
            i += 1
        valley = prices[i]
        while i < n - 1 and prices[i] <= prices[i + 1]:
            i += 1
        peak = prices[i]
        profit += peak - valley
    return profit

easy

A. 2

B. 0

C. 3

D. 1

Solution

1. Step 1: Trace first while loop to find valley

   i=0, prices[0]=1, prices[1]=2, 1 < 2 so inner loop skips, valley=1

2. Step 2: Trace second while loop to find peak

   i increments while prices[i] <= prices[i+1]: i=0 to 1 (2 <= 3), i=1 to 2 (3 no next), peak=3

3. Step 3: Calculate profit and return

   profit += 3 - 1 = 2, loop ends, return 2

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Profit matches sum of positive differences (2) [OK]

Hint: Sum of (3-1) = 2 profit [OK]

Common Mistakes:

• Off-by-one error missing last peak
• Confusing valley and peak assignments
• Returning zero if no decreasing sequence found

2. You are given a list of non-negative integers and need to arrange them to form the largest possible number when concatenated. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming to find the maximum concatenation by exploring all subsequences

B. Sorting the numbers as strings using a custom comparator that compares concatenations

C. Greedy approach by always picking the largest integer first

D. Brute force generating all permutations and selecting the maximum concatenation

Solution

1. Step 1: Understand the problem requires ordering numbers to maximize concatenation

   The key is to compare pairs by concatenating in both possible orders and deciding which order yields a larger combined string.

2. Step 2: Recognize that sorting with a custom comparator based on concatenation comparisons guarantees optimal order

   This approach ensures the final concatenation is lexicographically largest, unlike greedy or DP which do not handle pairwise ordering correctly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Custom comparator sorting is the standard solution for this problem [OK]

Hint: Compare concatenations as strings to decide order [OK]

Common Mistakes:

• Assuming greedy pick of largest integer works
• Using DP which is unnecessary
• Brute force is correct but inefficient

3. You have two arrays representing the top and bottom halves of dominoes. You want to make all values in one row uniform by rotating some dominoes. Which algorithmic approach guarantees an optimal solution with minimal rotations?

easy

A. Dynamic Programming that tries all possible uniform values and stores intermediate results

B. Greedy approach checking only the two candidate values from the first domino

C. Backtracking to try all rotation combinations exhaustively

D. Sorting both arrays and then matching values to minimize rotations

Solution

1. Step 1: Identify candidate values from the first domino

   The only possible uniform values are the top or bottom value of the first domino, since all dominoes must match one of these.

2. Step 2: Check feasibility and count rotations

   For each candidate, verify if all dominoes can be rotated to match it and count minimal rotations needed.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Checking only two candidates reduces complexity and guarantees correctness [OK]

Hint: Only two candidates from first domino suffice [OK]

Common Mistakes:

• Trying all numbers 1-6 unnecessarily
• Using DP or backtracking wasting time

4. You are given a string and need to partition it into as many parts as possible so that each letter appears in at most one part. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy algorithm using last occurrence indices to determine partition boundaries

B. Backtracking to try all possible partitions and select the best

C. Sliding window technique to find maximum substring without repeating characters

D. Dynamic Programming with memoization to find all valid partitions

Solution

1. Step 1: Understand problem constraints

   The problem requires partitions where no character appears in more than one part, so we must know the last occurrence of each character.

2. Step 2: Identify approach that uses last occurrence

   The greedy approach that tracks last occurrence indices and extends partitions accordingly guarantees optimal partitions without overlap.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy with last occurrence indices ensures minimal partitions covering all characters [OK]

Hint: Use last occurrence map to greedily partition [OK]

Common Mistakes:

• Assuming DP is needed for optimal partitions
• Using sliding window for unique substrings instead
• Trying backtracking which is inefficient here

5. The following code attempts to solve the Jump Game problem. Identify the line that contains a subtle bug that causes incorrect results on some inputs.

def canJump(nums):
    maxReach = 0
    for i, jump in enumerate(nums):
        # Bug: missing check if current index is beyond maxReach
        maxReach = max(maxReach, i + jump)
        if maxReach >= len(nums) - 1:
            return True
    return False

medium

A. Line 2: Initialization of maxReach

B. Line 3: for loop header enumerating nums

C. Line 4: Missing check if i > maxReach before updating maxReach

D. Line 6: Checking if maxReach reaches or exceeds last index

Solution

1. Step 1: Understand the missing condition

   The code does not check if the current index i is beyond maxReach, which means it may continue even when stuck.

2. Step 2: Identify the bug line

   Line 4 updates maxReach without verifying if i is reachable, causing false positives on inputs with unreachable indices.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Adding "if i > maxReach: return False" fixes the bug [OK]

Hint: Check if current index is reachable before updating maxReach [OK]

Common Mistakes:

• Forgetting to check i > maxReach
• Assuming maxReach update alone suffices