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 search_matrix
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_03.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
| 74 | 33 | 206 | 21 |
A device stores sorted measurements in rows. When a new reading arrives, can we find it without inspecting every record? Then a queue of records must be reordered while preserving the same node objects.
This week uses candidate intervals for search and changes links to reverse or merge lists.
Positions and node references
An array directly accesses position i by index. A linked list follows next references from its head. Two nodes with the same value 2 can still be distinct objects.
class ListNode:
def __init__(self, val=0, next=None):
self.val, self.next = val, next
The diagram processes node 2. Preserve node 3 as following before changing 2’s next to node 1. A node’s value and its links are different data. node = node.next moves a local reference; node.next = other changes the structure.
LeetCode 74: Search a 2D Matrix · Medium
Return whether target occurs in the matrix.
1 <= R,C <= 100; values/target -10^4..10^4; sorted rows, each next row starts above the previous end.
Predict before implementing
Treat the ordered matrix as six virtual positions. Convert midpoint with divmod(mid, column_count), without flattening a new list. Search 8 next and record when the inclusive interval becomes empty.
search_matrix([[1, 3, 5], [7, 9, 11]], 9)
# True
In Week 3, linked() builds linked nodes; in Week 4, tree() builds a tree from level-order notation. Both helpers are in structures.py.
Idea and state transitions
74 · Idea and execution trace
LeetCode 74: Search a 2D Matrix · Medium
Return whether target occurs in the matrix.
Each row is sorted and its first value exceeds the previous row’s last value. Reading rows consecutively therefore gives one sorted sequence. Search that virtual sequence without copying it; translate each position into a row and column.
matrix=[[1,3,5],[7,9,11]], target=9. Bounds are shown before each comparison.
| left,right | mid | row,col | Value | Next action |
|---|---|---|---|---|
| 0,5 | 2 | 0,2 | 5 | 5 < 9 → left=3 |
| 3,5 | 4 | 1,1 | 9 | Return True |
74 · Why it works; time and memory
The cross-row property makes the flattened order sorted. Comparisons eliminate an impossible half; every update shrinks the interval, and an empty interval means absence.
For N=R·C elements, comparisons reduce the candidates roughly to N/2, N/4, and so on. N=8 needs at most four comparisons; time is O(log(N+1)). Index arithmetic and each list lookup cost O(1).
No flattened list is built. Only a fixed number of indices and values are retained, so auxiliary space is O(1). Copying the matrix into a new sequence would change this space bound.
left=mid can stall on two candidates. [[1,9],[2,10]] has sorted rows but violates this contract.
matrix=[[1,4,7],[9,12,18]], target=12 → True
Termination when the target is absent
Search for target=8 in [[1,3,5],[7,9,11]]. The interval [left,right] includes both remaining endpoints.
| Interval before comparison | mid and value | Reason for removal | Next interval |
|---|---|---|---|
| [0,5] | 2, value 5 | All positions at or below 2 have values below 8 | [3,5] |
| [3,5] | 4, value 9 | All positions at or above 4 have values above 8 | [3,3] |
| [3,3] | 3, value 7 | The last candidate also fails | [4,3] |
left>right means no candidate remains, so return False. left==right still requires one comparison. Updating left=mid can repeat mid=3 forever on [3,4].
Halving N candidates takes about log₂N reductions to reach one. Including its comparison, the worst count is floor(log₂N)+1 for N≥1.
Implement and execute
from structures import ListNode
def search_matrix(matrix, target):
rows, cols = len(matrix), len(matrix[0])
left, right = 0, rows * cols - 1
while left <= right:
mid = (left + right) // 2
value = matrix[mid // cols][mid % cols]
if value == target:
return True
if value < target:
left = mid + 1
else:
right = mid - 1
return False
python trace_lab.py --case search_matrix
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 33: Search in Rotated Sorted Array · Medium
Return target’s index in a rotated sorted array, or -1.
1 <= n <= 5000; values/target -10^4..10^4; all values distinct.
Predict before implementing
Check which half is ordered, then whether target lies within that half. Update one boundary beyond mid. Repeat for missing target 3 and explain the -1 result. Distinct values make the ordered-half test decisive.
search_rotated([4, 5, 6, 7, 0, 1, 2], 0)
# 4
In Week 3, linked() builds linked nodes; in Week 4, tree() builds a tree from level-order notation. Both helpers are in structures.py.
Idea and state transitions
33 · Idea and execution trace
LeetCode 33: Search in Rotated Sorted Array · Medium
Return target’s index in a rotated sorted array, or -1.
Although a rotated array is not globally sorted, with distinct values at least one half around mid is sorted. Identify that half, then test whether target lies within its value range to decide which half to discard.
nums=[4,5,6,7,0,1,2], target=0
| left,mid,right | Sorted half | Target test | Update |
|---|---|---|---|
| 0,3,6 | Left: 4..7 | 0 is outside | left=4 |
| 4,5,6 | Left: 0..1 | 0 is inside | right=4 |
| 4,4,4 | nums[4]=0 | Match | Return 4 |
33 · Why it works; time and memory
Distinct values and one rotation ensure a sorted half. Range tests discard only an impossible half; mid±1 guarantees progress.
Each iteration retains only one half, excluding mid. There are O(log(n+1)) iterations, each with a fixed number of comparisons and lookups.
No new array or recursive call stack is created, so auxiliary space is O(1). With duplicates, an input such as [1,1,1,0,1] can have equal endpoints and midpoint, hiding which half is sorted. This code and bound depend on distinct values.
With duplicates, [1,0,1,1,1] makes the sorted-side test ambiguous; duplicates are outside this contract.
nums=[6,8,1,3,5], target=3 → 3
Implement and execute
from structures import ListNode
def search_rotated(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
python trace_lab.py --case search_rotated
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 206: Reverse Linked List · Easy
Reverse a singly linked list and return its new head.
0..5000 nodes; values -5000..5000.
Predict before implementing
Save current.next before rewriting it to previous. Then advance previous and current. Draw 2→5→8, then 2→None with current at 5. Check that the reversed chain ends at None.
reverse_list(linked([2, 5, 8]),)
# [8, 5, 2]
In Week 3, linked() builds linked nodes; in Week 4, tree() builds a tree from level-order notation. Both helpers are in structures.py.
Idea and state transitions
206 · Idea and execution trace
LeetCode 206: Reverse Linked List · Easy
Reverse a singly linked list and return its new head.
A linked list’s order is determined by next links. Reverse each link without allocating replacement nodes. Save the original successor before changing the link, or the unprocessed remainder becomes unreachable.
Input: 1 → 2 → 3 → None. Each row is the state after one loop body.
| Node processed | Chain at previous | Chain at current |
|---|---|---|
| None yet | None | 1 → 2 → 3 |
| 1 | 1 → None | 2 → 3 |
| 2 | 2 → 1 → None | 3 |
| 3 | 3 → 2 → 1 → None | None |
206 · Why it works; time and memory
previous holds the reversed prefix and current the untouched suffix. Moving one node preserves all nodes; when current is None, previous is the full reversed list.
Each of n nodes is visited once, with a fixed number of reference assignments per visit, giving O(n) time. Reversing the first link does not reverse later links; every node must be processed.
Only previous, current, and following are added. Existing nodes are reused, so auxiliary space is O(1) and no output nodes are allocated. The O(n) input structure is distinct from extra workspace. A recursive implementation would need O(n) call-stack space.
Overwriting without saving next loses the suffix. Two nodes with equal values are still different objects.
head=[4,6,9] → [9,6,4]
Implement and execute
from structures import ListNode
def reverse_list(head):
previous, current = None, head
while current:
following = current.next
current.next = previous
previous, current = current, following
return previous
python trace_lab.py --case reverse_list
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 21: Merge Two Sorted Lists · Easy
Splice two sorted linked lists into one sorted list.
Each list has 0..50 nodes, values -100..100, nondecreasing.
Predict before implementing
Use a dummy node and a tail. Attach the smaller head and advance only that input. Once one list ends, attach the remaining chain. Compare duplicate values and an empty input.
merge_lists(linked([1, 3]), linked([2, 4]))
# [1, 2, 3, 4]
In Week 3, linked() builds linked nodes; in Week 4, tree() builds a tree from level-order notation. Both helpers are in structures.py.
Idea and state transitions
21 · Idea and execution trace
LeetCode 21: Merge Two Sorted Lists · Easy
Splice two sorted linked lists into one sorted list.
The smallest remaining value must be at one of the two sorted-list heads. Attach the smaller head to the result tail and advance only that input. There is no need to search farther down either list.
A=1 → 4, B=2 → 3. Links beyond tail may still point into an input until the next assignment replaces them.
| Choice | Finalized result prefix | A head | B head |
|---|---|---|---|
| Initial | Empty | 1 | 2 |
| A: 1 | 1 | 4 | 2 |
| B: 2 | 1 → 2 | 4 | 3 |
| B: 3 | 1 → 2 → 3 | 4 | None |
| Attach remaining A | 1 → 2 → 3 → 4 | 4 | None |
21 · Why it works; time and memory
The prefix through tail is sorted. The smaller head is minimal among all remaining nodes; the leftover suffix is already sorted.
For lengths n and m, each iteration finalizes one node. Alternating choices can require O(n+m) work. The final remainder attachment itself costs O(1).
One dummy node and a fixed number of references give O(1) auxiliary space. The result has n+m nodes, but these are reused input nodes. Preserving both input chains would require a copying implementation with O(n+m) new-node space.
Returning dummy includes a fake node. This implementation assumes acyclic input lists with no shared nodes.
first=[1,5], second=[2,3] → [1,2,3,5]
Implement and execute
from structures import ListNode
def merge_lists(first, second):
dummy = tail = ListNode()
while first and second:
if first.val <= second.val:
tail.next, first = first, first.next
else:
tail.next, second = second, second.next
tail = tail.next
tail.next = first or second
return dummy.next
python trace_lab.py --case merge_lists
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.