Week 8 Student Exercises

Set up and run

Extract the lab code ZIP and work in its code folder. Use Python 3.11+ and the standard library.

python trace_lab.py --case can_jump
python verify.py
python verify.py --student

Predict the small example and its states on paper first. trace_lab.py traces the actual solutions.py implementation. before L… shows values immediately before that line executes: identify what the preceding executed line changed. Linked lists display a chain; tree nodes display their value and child values. Exclude tracing, copying, and printing overhead from the algorithm’s complexity.

Implement the functions and methods in student_week_08.py, then run verify.py --student. An initial NotImplementedError identifies work still to implement. Without --student, the verifier checks the supplied solutions. Use python trace_lab.py --case FUNCTION --student to inspect your implementation.

For each task record the input/output meaning, state invariant, one state transition, final answer, time, auxiliary space, and output space. Passing one small example does not establish correctness for all inputs.

This week’s problems

Worked solutions

55 45 134 200

When each position allows a different travel distance, determine reachability and the fewest moves. On a circular route, find a starting point that never runs out of fuel.

Solving these tasks without storing every choice requires a reason that discarded candidates cannot be needed. Reachable ranges and prefix sums provide that reason.

Why discarded candidates stay unnecessary

A greedy algorithm eliminates alternatives before storing all choices. It needs a reason why a discarded choice cannot later improve the answer. Merely choosing a large value does not establish that reason.

Fuel differences around a circuit and a feasible start

Problem Summary retained Reason for elimination
Reachability Interval 0..farthest Earlier positions cover a continuous prefix
Minimum jumps Current end, next farthest Inspect every position with fewer jumps first
Fuel circuit Candidate start and tank Every start inside a failed segment also fails

The pictured total balance is zero. Start 0 fails immediately, whereas start 1 completes the circuit with balances 3,2,0. Testing total fuel and selecting a starting point serve different roles.

LeetCode 55: Jump Game · Medium

Decide whether maximum forward jump lengths permit reaching the last index.

1 <= n <= 104; values 0..105.

Predict before implementing

Maintain the farthest reachable index. Only positions at or below that boundary can extend it. The boundary stays at 3, so index 4 cannot supply a jump. Change the zero to 1 and explain the difference.

can_jump([3, 2, 1, 0, 4],)
# False

Idea and state transitions

55 · Idea and execution trace

LeetCode 55: Jump Game · Medium

Decide whether maximum forward jump lengths permit reaching the last index.

Each value is a maximum jump length, not a mandatory jump. Reachable intervals therefore form a continuous prefix starting at zero. Keep only its farthest endpoint to decide whether the current index can be visited.

nums=[2,0,1,0]. Test reachability using the old farthest before updating it.

index step Old farthest New farthest
0 2 0 max(0,0+2)=2
1 0 2 max(2,1+0)=2
2 1 2 max(2,2+1)=3
3 0 3 max(3,3+0)=3

Index 3 is reachable, so return True.

55 · Why it works; time and memory

Reachable positions form the interval 0..farthest. Allowed jumps include every shorter distance, preserving an interval; an index beyond it cannot be crossed.

Read n elements once, using only comparison, addition, and max at each step. Paths are not enumerated, so time is O(n); early failure may shorten a run.

Instead of storing every reachable position in a set, retain one endpoint of a continuous interval. A fixed number of variables gives O(1) auxiliary space. Allowing all smaller jump lengths is what makes this interval summary valid.

In [2,3,0,0,0], taking the longest first jump stops at the zero at index 2. Exploring reachable index 1 also exposes a path to the last index. The algorithm maintains the range reachable from all eligible positions.

nums=[2,0,1,0] → True

Implement and execute

from collections import deque
import heapq

def can_jump(nums):
    farthest = 0
    for index, step in enumerate(nums):
        if index > farthest:
            return False
        farthest = max(farthest, index + step)
    return True
python trace_lab.py --case can_jump

Compare the trace return value with your prediction. Make the input change proposed above, find the first line where the state differs, and explain its effect on the answer.

LeetCode 45: Jump Game II · Medium

Return the minimum jumps needed to reach the last index.

1 <= n <= 104; values 0..1000; last index guaranteed reachable.

Predict before implementing

Track the end reachable with the current jump count and the farthest endpoint found within it. Increment jumps only when the current interval ends. Intervals end at 0,2,4; two jumps reach the last index.

min_jumps([2, 3, 1, 1, 4],)
# 2

Idea and state transitions

45 · Idea and execution trace

LeetCode 45: Jump Game II · Medium

Return the minimum jumps needed to reach the last index.

Treat all positions reachable with one more jump as a layer. Inspect the whole current layer before fixing the next farthest endpoint. The first layer covering the destination gives the minimum jump count; no single longest jump is chosen in advance.

nums=[2,3,0,1,0]. end marks the layer boundary for the current jump count.

index Updated farthest Old end Updated jumps,end
0 2 0 1,2
1 4 2 1,2
2 4 2 2,4
3 4 4 2,4

Route 0 → 1 → 4 needs two jumps; committing to 0 → 2 gets stuck.

45 · Why it works; time and memory

Scan every reachable position in the current level before fixing the next frontier. These are BFS levels in an implicit unweighted graph, so the jump count is minimal.

Explicitly constructing all possible jump edges could create many edges per position. This implementation summarizes each continuous layer with endpoints and scans only n-1 indices, taking O(n) time. Expanding farthest never restarts earlier scans.

Only end, farthest, jumps, and loop variables are stored, giving O(1) auxiliary space. It uses BFS layers conceptually without building a queue. Length one executes zero iterations and returns zero jumps.

The target is n-1. Processing the last index overcounts; [0] gives zero. Unreachable inputs are outside this contract.

nums=[2,3,0,1,0] → 2

In the example, layer 0 is {0}, the positions newly reached with one jump are {1,2}, and the next layer is {3,4}. Even after index=1 discovers endpoint 4, the scan finishes the current layer through index=2 before committing jumps=2. end is the last index to examine in a layer, not a chosen landing position.

Implement and execute

from collections import deque
import heapq

def min_jumps(nums):
    end = farthest = jumps = 0
    for index in range(len(nums) - 1):
        farthest = max(farthest, index + nums[index])
        if index == end:
            jumps += 1
            end = farthest
    return jumps
python trace_lab.py --case min_jumps

Compare the trace return value with your prediction. Make the input change proposed above, find the first line where the state differs, and explain its effect on the answer.

LeetCode 134: Gas Station · Medium

Return a start completing a circular route from an empty tank, or -1.

1 <= n <= 105; equal gas/cost lengths; values 0..104; solution unique if present.

Predict before implementing

Accumulate total surplus and the balance since the current start. A negative segment balance discards every start in that segment. Surpluses are -2,-2,-2,3,3; restart at 3, then verify one full circular lap.

gas_start([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])
# 3

Idea and state transitions

134 · Idea and execution trace

LeetCode 134: Gas Station · Medium

Return a start completing a circular route from an empty tank, or -1.

When a segment first runs out of fuel, every intermediate starting point also fails by that endpoint. The original start accumulated a nonnegative balance before reaching each intermediate point; starting there with no balance cannot improve the failed suffix. Discard the whole failed segment at once.

gas=[1,4,2], cost=[3,1,3]. total is the global balance; tank is the current candidate’s balance.

index gas-cost total tank after failure check start
0 -2 -2 0 (reset) 1
1 +3 1 3 1
2 -1 0 2 1

Starting at 1, balances along 1 → 2 → 0 are 3 → 2 → 0.

134 · Why it works; time and memory

At the first failure over s..i, each earlier prefix s..j-1 is nonnegative. Removing such a prefix leaves j..i negative too, eliminating all intermediate starts. If total is nonnegative, the final candidate also has enough surplus to wrap through the eliminated prefixes.

Trying n steps independently from each start would cost O(n2). Eliminating every start in a failed segment lets index advance without restarting, so there are n constant-cost updates: O(n) time.

zip reads one pair at a time without constructing a difference array. A fixed number of counters gives O(1) auxiliary space. Check both the size of the returned index and the absence of growing intermediate storage.

Choosing the largest gas supply is unjustified: gas=[5,0,4],cost=[6,1,2] fails at station 0; station 2 is the unique valid start.

gas=[1,4,2], cost=[3,1,3] → 1

Removing a failed segment and wrapping around

For differences [2,−1,−3,3], starting at 0 gives fuel 2→1→−2. The first failure at 2 eliminates starts 0,1,2. Start 1 would also fail with −1−3=−4; start 2 fails with −3.

Prefix sum P[k] is the sum of the first k differences. Here P=[0,2,1,−2,1] has its minimum at 3, which is also the algorithm’s new start.

Station visited from start 3 Calculation Fuel
3 3 3
0 3+2 5
1 3+2−1 4
2 3+2−1−3 1

In general, fuel after a minimum-prefix position s is P[k]−P[s]≥0. After wrapping, fuel is the full sum P[n] plus P[k]−P[s]. If the full sum is nonnegative, this is also nonnegative, proving that the final candidate completes the wrapped portion too.

Implement and execute

from collections import deque
import heapq

def gas_start(gas, cost):
    total = tank = start = 0
    for index, (supply, use) in enumerate(zip(gas, cost)):
        total += supply - use
        tank += supply - use
        if tank < 0:
            start, tank = index + 1, 0
    return start if total >= 0 else -1
python trace_lab.py --case gas_start

Compare the trace return value with your prediction. Make the input change proposed above, find the first line where the state differs, and explain its effect on the answer.

LeetCode 200: Number of Islands · Medium

Repeat

Count land components connected horizontally or vertically in a character grid.

1 <= R,C <= 300; cells are strings “0” or “1”.

Predict before implementing

Choose connected-component search rather than a greedy frontier. Draw the region (0,0),(0,1),(1,1) and the separate cell (2,2). Explain why diagonal contact is not an edge, then test an all-water grid.

islands([list('110'), list('010'), list('001')],)
# 2

Idea and state transitions

200 · Idea and execution trace

LeetCode 200: Number of Islands · Medium

Count land components connected horizontally or vertically in a character grid.

Starting from one land cell and following all four-directional connections reaches its whole island. Start a traversal and increase the count only at unvisited land, preventing duplicate counting. Diagonals do not connect cells.

Grid: [["1","1","0"],["0","1","0"],["1","0","1"]]. Coordinates start at zero; stack top is on the right.

Action stack Newly added to seen count
Start (0,0) [(0,0)] (0,0) 1
Pop (0,0) [(0,1)] (0,1) 1
Pop (0,1) [(1,1)] (1,1) 1
Pop (1,1) [] None 1
Traverse (2,0), (2,2) separately [] (2,0), (2,2) 3

200 · Why it works; time and memory

A traversal reaches exactly its starting component. Marked components cannot restart; the number of starts equals the component count.

The outer scan reads R·C cells. Each land cell is pushed and popped once because of seen, and each pop checks four neighbors. Four is independent of input size, giving expected O(RC) time under expected hash-set costs. The inner traversal is not restarted fully for every cell.

Both seen and the pending stack can hold up to RC coordinates, so auxiliary space is O(RC). Marking the grid itself could replace seen, but would mutate the input and would not eliminate stack storage.

Use == for values; is tests identity. Diagonal land in a 2x2 grid forms two components.

grid=[["1","0","1"],["1","0","0"]] → 2

Implement and execute

from collections import deque
import heapq

def islands(grid):
    rows, cols = len(grid), len(grid[0])
    seen, count = set(), 0
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] != "1" or (row, col) in seen:
                continue
            count += 1
            stack = [(row, col)]
            seen.add((row, col))
            while stack:
                r, c = stack.pop()
                for nr, nc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
                    if (0 <= nr < rows and 0 <= nc < cols
                            and grid[nr][nc] == "1" and (nr,nc) not in seen):
                        seen.add((nr,nc))
                        stack.append((nr,nc))
    return count
python trace_lab.py --case islands

Compare the trace return value with your prediction. Make the input change proposed above, find the first line where the state differs, and explain its effect on the answer.

Lab report

Include the small-input state table, completed code, your own boundary input and expected result, and verification results. Explain time by total operation counts and space by simultaneously live state. Include any input copying or sorting costs.

Job-selection transfer exercise