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. Given the following code for partitioning labels, what is the returned list when the input string is "eccbbbbdec"?

def partitionLabels(s):
    last = [0] * 26
    for i, c in enumerate(s):
        last[ord(c) - ord('a')] = i
    res = []
    start = 0
    end = 0
    for i, c in enumerate(s):
        end = max(end, last[ord(c) - ord('a')])
        if i == end:
            res.append(end - start + 1)
            start = i + 1
    return res

easy

A. [10]

B. [9, 1]

C. [1, 9]

D. [3, 7]

Solution

1. Step 1: Compute last occurrences

   Characters: e last at 8, c last at 9, b last at 6, d last at 7.

2. Step 2: Trace partitions

   Start=0, end=0 initially. Iterate: - i=0 (e): end=max(0,8)=8 - i=1 (c): end=max(8,9)=9 - i=2 (c): end=9 - i=3 (b): end=max(9,6)=9 - i=4 (b): end=9 - i=5 (b): end=9 - i=6 (b): end=9 - i=7 (d): end=max(9,7)=9 - i=8 (e): end=9 - i=9 (c): i==end, partition size=9-0+1=10 Append 10, start=10 (end of string) But since string length is 10, only one partition of size 10. However, careful: last occurrence of 'e' is 8, 'c' is 9, so partition ends at 9. So only one partition of size 10.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Partition covers entire string length 10 [OK]

Hint: Track max last occurrence to find partition end [OK]

Common Mistakes:

• Miscounting partition size by off-by-one
• Stopping partition too early ignoring max last occurrence
• Confusing character indices

2. You have a list of tasks represented by characters, each task takes 1 unit of time to execute. The CPU must wait for at least n units of time before executing the same task again. Which approach guarantees the minimum total time to finish all tasks?

easy

A. Dynamic Programming that tries all permutations of task orders to find the minimal schedule

B. Greedy algorithm using a max-heap to always schedule the most frequent available task next

C. Simple round-robin scheduling without considering cooldown intervals

D. Sorting tasks by frequency and inserting idle slots greedily without priority queue

Solution

1. Step 1: Understand the cooldown constraint

   The CPU must wait n units before repeating the same task, so scheduling must consider task frequencies and cooldowns.

2. Step 2: Why max-heap greedy works best

   Using a max-heap prioritizes tasks with the highest remaining frequency, ensuring minimal idle time by always picking the most urgent task available.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Max-heap approach matches known optimal solution [OK]

Hint: Max-heap greedily schedules highest frequency tasks first [OK]

Common Mistakes:

• Assuming DP or brute force is needed
• Ignoring cooldown leads to incorrect minimal time
• Greedy without priority queue misses optimal order

3. The following code attempts to implement the peak-valley approach but contains a subtle bug. Identify the line causing incorrect profit calculation.

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

medium

A. Line with 'while i < n - 1 and prices[i] < prices[i + 1]:'

B. Line with 'valley = prices[i]'

C. Line with 'while i < n - 1 and prices[i] > prices[i + 1]:'

D. Line with 'profit += peak - valley'

Solution

1. Step 1: Compare with correct condition

   The correct condition should be prices[i] >= prices[i + 1] to skip equal or descending prices.

2. Step 2: Identify bug impact

   Using strict '>' misses equal prices, causing incorrect valley selection and possibly negative profit.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Changing '>' to '>=' fixes edge cases with flat prices [OK]

Hint: Check comparison operators in loops for off-by-one errors [OK]

Common Mistakes:

• Using strict inequalities causing missed equal prices
• Adding negative differences to profit
• Off-by-one errors causing index out of range

4. What is the time complexity of the optimal greedy solution for the Jump Game problem, and why is the following common misconception incorrect? Misconception: The time complexity is O(n^2) because for each index, you might check all reachable next indices.

medium

A. O(n) because the algorithm iterates through the array once, updating max reachable index

B. O(n log n) due to sorting or binary search involved in jump calculations

C. O(n^2) because each index can jump to multiple next indices

D. O(n) but with O(n) auxiliary space for memoization

Solution

1. Step 1: Identify the algorithm's iteration pattern

   The greedy solution iterates through the array once, updating a single variable maxReach without nested loops.

2. Step 2: Explain why O(n^2) is incorrect

   Unlike brute force, it does not explore all jumps explicitly; it only tracks the furthest reachable index, so no nested iteration occurs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass through array -> O(n) time, no nested loops [OK]

Hint: Greedy uses one pass, no nested loops [OK]

Common Mistakes:

• Confusing brute force with greedy complexity
• Assuming nested loops due to jumps

5. What is the time complexity of the optimal single-pass greedy solution for the Minimum Domino Rotations problem, given arrays of length n?

medium

A. O(6 * n) because it checks all numbers 1 to 6

B. O(n^2) due to nested loops over dominoes and candidates

C. O(n) because it only checks two candidate values with a single pass

D. O(1) since it only checks the first domino values

Solution

1. Step 1: Identify loops in the code

   The code checks at most two candidates (A[0] and B[0]) and iterates once over all n dominoes per candidate.

2. Step 2: Calculate total operations

   Each candidate check is O(n), so total is O(2 * n) = O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Only two passes over n elements -> linear time [OK]

Hint: Only two candidates checked, linear scan each [OK]

Common Mistakes:

• Assuming all 6 numbers checked -> O(6n)
• Confusing nested loops causing O(n^2)