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 kth_largest
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_05.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
| 215 | 56 | 200 | 994 |
Maintain the top k measurements as values arrive, and merge overlapping maintenance intervals. On a sensor map, identify separate failure regions and the time needed for failures to spread.
Full ordering, partial ranking, and connectivity need different state. Track a heap boundary, the end of a sorted interval, and traversal visits.
What counts as one step on a grid?
Treat cells as vertices and four-directional adjacencies as edges. Islands ask for connected components; propagation asks for distance from the nearest source.
Diagonal land cells on the left belong to separate islands. Numbers on the right are first infection times for [[2,1,1],[0,1,1]]; - marks an empty cell.
| Goal | Processing order | Retained information |
|---|---|---|
| Find all connected land | Stack: depth first | Visited coordinates and pending neighbors |
| Spread simultaneously by minute | Queue: breadth first | Current sources and remaining fresh cells |
Mark cells when discovered so different neighbors cannot enqueue or push the same cell repeatedly.
LeetCode 215: Kth Largest Element in an Array · Medium
Return the kth value in descending order, counting duplicates.
1 <= k <= n <= ; values -...
Predict before implementing
Keep a min-heap of the largest k values seen so far. Replace its root only with a larger value. The root is the smallest retained value, hence the kth largest overall. Try k=1 and duplicates.
kth_largest([3, 2, 1, 5, 6, 4], 2)
# 5
Idea and state transitions
215 · Idea and execution trace
LeetCode 215: Kth Largest Element in an Array · Medium
Return the kth value in descending order, counting duplicates.
Sorting everything finds the kth value, but only the largest k values need to be retained. In a min-heap containing those values, the root is their minimum and hence the current kth largest. Replace it only when a larger value arrives.
nums=[3,1,5,2,4], k=2. The table shows the actual heap list, not a fully sorted sequence.
| Operation | heap | Current kth value |
|---|---|---|
| Heapify first two | [1,3] | 1 |
| 5 > 1: replace | [3,5] | 3 |
| 2 <= 3: retain | [3,5] | 3 |
| 4 > 3: replace | [4,5] | 4 |
Heap positions and root replacement
In min-heap [2,4,3,8,6,5,7], the children of position i are 2i+1 and 2i+2. Root 2 has children 4 and 3. Siblings need not be sorted; each parent must be no larger than its children.
Replace the root with 9 and trace a repair path that promotes the smaller child.
| Step | Array | Next comparison |
|---|---|---|
| Replace root | [9,4,3,8,6,5,7] | choose 3 over 4 |
| Promote 3 | [3,4,9,8,6,5,7] | choose 5 over 7 |
| Promote 5 | [3,4,5,8,6,9,7] | 9 is a leaf; stop |
Reading root 3 takes O(1); repair follows a path of at most the tree height. heapify repairs parents from the bottom. With seven nodes, four leaves have height 0, two parents have height 1, and the root has height 2. This allows 2×1+1×2=4 downward levels in total. In general, the number of tall subtrees decreases geometrically, giving O(k) total work.
Python heapq representation and operations
215 · Why it works; time and memory
The heap retains the largest k values seen. A new value at most its minimum cannot improve that set; a larger one replaces the minimum. The final root is kth largest.
Copying and heapify cost O(k). Each of the remaining n-k values requires one root comparison and, only on replacement, a path of height O(log k). Time is O(k+(n-k)(1+log k)), commonly O(n log k) for k>=2. For k=1 it is O(n), like tracking a maximum.
The heap always has k entries, so auxiliary space is O(k); the result is one value. Heapify is linear because most nodes are near the bottom and have only short downward paths.
In a min-heap, each parent is no greater than its children, and the root holds a global minimum. Deduplicating changes the example’s answer.
nums=[8,3,8,2,5], k=2 → 8
Implement and execute
from collections import deque
import heapq
def kth_largest(nums, k):
heap = nums[:k]
heapq.heapify(heap)
for index in range(k, len(nums)):
value = nums[index]
if value > heap[0]:
heapq.heapreplace(heap, value)
return heap[0]
python trace_lab.py --case kth_largest
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 56: Merge Intervals · Medium
Return disjoint closed intervals covering the input union.
1 <= n <= ; 0 <= start <= end <= ; touching endpoints merge.
Predict before implementing
Sort by start. Compare each interval with the last merged end; extend with max(end, next_end) on overlap. Test [1,6] with [2,3] so the end never shrinks.
merge_intervals([[1, 3], [2, 6], [8, 10]],)
# [[1, 6], [8, 10]]
Idea and state transitions
56 · Idea and execution trace
LeetCode 56: Merge Intervals · Medium
Return disjoint closed intervals covering the input union.
After sorting by start, the next interval begins no earlier than processed intervals. It can therefore overlap only the last merged interval. Extend that interval’s end on overlap, or begin a new result interval when there is a gap.
Input: [[1,4],[2,3],[4,6],[8,9]]. Each row shows result after processing that interval.
| Interval | Test | result |
|---|---|---|
| [1,4] | First interval | [[1,4]] |
| [2,3] | 2 <= 4 | [[1,4]] |
| [4,6] | 4 <= 4 | [[1,6]] |
| [8,9] | 8 > 6 | [[1,6],[8,9]] |
56 · Why it works; time and memory
result equals the union of the processed prefix. Increasing starts mean a new interval can overlap only the last result; a gap makes a new disjoint component.
Sorting n intervals costs O(n log n). The subsequent scan runs n times and compares only one last result interval each time, so it costs O(n). Sorting dominates the total O(n log n).
sorted creates a list of n references and uses sorting workspace, giving O(n) auxiliary space. If z merged intervals remain, output space is O(z), with z<=n. Each output interval stores its own two endpoints.
Overwriting the end with 3 for [[1,8],[2,3]] loses coverage. Half-open time intervals may use a different touching rule.
intervals=[[5,7],[1,3],[3,6]] → [[1,7]]
Implement and execute
from collections import deque
import heapq
def merge_intervals(intervals):
result = []
for start, end in sorted(intervals, key=lambda item: item[0]):
if result and start <= result[-1][1]:
result[-1][1] = max(result[-1][1], end)
else:
result.append([start, end])
return result
python trace_lab.py --case merge_intervals
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
Count land components connected horizontally or vertically in a character grid.
1 <= R,C <= 300; cells are strings “0” or “1”.
Predict before implementing
Scan cells. On unseen land, increment the component count and flood-fill its four-neighbor region. Mark when scheduling a cell to avoid duplicate work. Diagonally touching land remains separate.
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.
LeetCode 994: Rotting Oranges · Medium
Return the minimum minutes for all fresh cells to change under simultaneous spread, or -1.
1 <= R,C <= 10; 0 empty,1 fresh,2 rotten; one orthogonal edge per minute.
Predict before implementing
Put all initially rotten cells in one queue. Process a whole level per minute and decrease fresh on each newly rotten cell. The fresh counts are 6→4→2→1→0. Try an isolated fresh cell: return -1.
rot_minutes([[2, 1, 1], [1, 1, 0], [0, 1, 1]],)
# 4
Idea and state transitions
994 · Idea and execution trace
LeetCode 994: Rotting Oranges · Medium
Return the minimum minutes for all fresh cells to change under simultaneous spread, or -1.
All initially rotten cells are sources at time zero. Put them all in one queue and expand by levels. The first infection time of a cell is its distance from the nearest source. Processing sources sequentially would misrepresent simultaneous spread.
Input: [[2,1,1],[0,1,1]]. Each queue contains cells newly rotten at that time, awaiting processing.
| Time minutes | queue | fresh |
|---|---|---|
| 0 | [(0,0)] | 4 |
| 1 | [(0,1)] | 3 |
| 2 | [(1,1),(0,2)] | 1 |
| 3 | [(1,2)] | 0 |
Once fresh is zero, return 3 without processing the final queue.
994 · Why it works; time and memory
BFS levels are minimum edge distances from any source. Equal edge durations make first discovery earliest; remaining fresh cells after exhaustion are unreachable.
Copying and the initial scan each cost O(RC). Every cell enters the queue once and checks four neighbors when removed, so propagation also costs O(RC). Adding these stages gives O(RC); do not multiply by the number of minutes again.
The board copy stores RC cells to preserve the input. The queue may also hold O(RC) cells, giving O(RC) auxiliary space. Constant-size fresh and minutes counters do not make the whole algorithm constant-space.
[[2,0,1]] gives -1; [[0,2]] gives 0. Processing newly queued levels in the same minute undercounts time.
grid=[[2,1,1],[0,1,0]] → 2
board=[row[:] for row in grid] copies each row as well, preserving the original cell values. fresh += board[r][c] == 1 adds 1 for True and 0 for False. Scanning [2,1,1] therefore makes fresh go 0→1→2.
An empty queue with fresh cells remaining means unreachable cells and returns -1. If fresh is initially zero, no time step is needed and the result is 0.
Implement and execute
from collections import deque
import heapq
def rot_minutes(grid):
rows, cols = len(grid), len(grid[0])
board = [row[:] for row in grid]
queue, fresh, minutes = deque(), 0, 0
for r in range(rows):
for c in range(cols):
if board[r][c] == 2:
queue.append((r,c))
fresh += board[r][c] == 1
while queue and fresh:
for _ in range(len(queue)):
r, c = queue.popleft()
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 board[nr][nc] == 1:
board[nr][nc] = 2
fresh -= 1
queue.append((nr,nc))
minutes += 1
return minutes if fresh == 0 else -1
python trace_lab.py --case rot_minutes
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.