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 two_sum
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_01.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
Operation costs and worked solutions
Removing every element can have different total costs depending on the operation. Repeated removal from the front of a list shifts n-1, n-2, …, 0 references.
| Repeated operation | One operation | Count or total shifts | Total |
|---|---|---|---|
| list pop from end | Amortized O(1) | n calls | O(n) |
| list pop(0) | Current length | n(n-1)/2 shifts | O() |
| deque popleft | O(1) | n calls | O(n) |
| Search earlier list per value | Up to O(n) | n calls | O() |
| dict key lookup per value | Expected O(1) | n calls | Expected O(n) |
Summing n values while retaining only a running sum takes O(n) time and O(1) auxiliary space. Count iterations and retained storage separately.
Sharing resize costs across calls
Count eight appends to an array whose capacity doubles through 1,2,4,8. This is a calculation for geometric growth, not CPython’s exact allocation schedule.
| Length after append | New capacity needed | Existing references moved |
|---|---|---|
| 1 | 1 | 0 |
| 2 | 2 | 1 |
| 3 | 4 | 2 |
| 4 | unchanged | 0 |
| 5 | 8 | 4 |
| 6–8 | unchanged | 0 |
Eight new writes plus 1+2+4=7 copies give 15 operations. When N is a power of two, copies total N−1 and all writes total 2N−1. Between powers of two, copies remain below 2N, so total cost is O(N). Growing by just one slot would instead copy 1+2+…+(N−1) references, giving O(N²).
Dividing O(N) total work by N calls gives amortized O(1) per append.
LeetCode 1: Two Sum · Easy
Return two distinct indices whose values sum to target.
2 <= n <= 10^4; values and target: -10^9..10^9; exactly one answer.
Predict before implementing
For each value, compute target minus value. Look up that complement in a dictionary of earlier indices, then store the current index. Test [3,3] with target 6 to check that the two indices differ.
two_sum([4, 8, 3], 7)
# [0, 2]
Idea and state transitions
1 · Staged hints
Return two distinct indices whose values sum to target. An element cannot be reused; official inputs have one answer.
LeetCode 1: Two Sum · Easy
H1. Which value would complete the current value?
H2. When should an index be recorded to avoid using it twice?
H3. Store earlier value-to-index pairs; look up target-value before recording the current value.
nums=[4,8,3], target=7
| index | value | Needed | seen before lookup | Result |
|---|---|---|---|---|
| 0 | 4 | 3 | {} | Absent → record 4:0 |
| 1 | 8 | -1 | {4:0} | Absent → record 8:1 |
| 2 | 3 | 4 | {4:0,8:1} | Found → [0,2] |
1 · Correctness and cost
At loop entry, the map contains only earlier positions. At the later position of the unique answer, its partner is present. This reuses information instead of checking all O() pairs.
Each element performs a fixed number of dictionary operations. Expected O(1) operations repeated n times give expected O(n) time. Up to n distinct value-position entries use O(n) auxiliary space; two returned indices use O(1). Severe hash collisions give an O() worst-case upper bound.
1 · Counterexamples and checks
Recording first can reuse one index on [3,3], target=6.
nums=[4,8,3], target=7 → [0,2]
Implement and execute
def two_sum(nums, target):
seen = {}
for index, value in enumerate(nums):
if target - value in seen:
return [seen[target - value], index]
seen[value] = index
return []
python trace_lab.py --case two_sum
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 219: Contains Duplicate II · Easy
Decide whether equal values occur at distinct indices at distance at most k.
1 <= n <= 10^5; values -10^9..10^9; 0 <= k <= 10^5.
Predict before implementing
Store the most recent index for each value. Compare the index distance before replacing it. At index 3, the preceding 4 is at index 2, not index 0. Change k to 0 and explain False.
nearby_duplicate([4, 7, 4, 4], 1)
# True
Idea and state transitions
219 · Staged hints
Return True exactly when equal values occur at distinct positions i,j with distance at most k.
LeetCode 219: Contains Duplicate II · Easy
H1. Which occurrence of a value should be retained?
H2. Can an older occurrence be closer than the latest one?
H3. Retain the latest index per value; compare distance, then update.
nums=[4,7,4,4], k=1
| index | value | Prior latest[value] | Distance | Action |
|---|---|---|---|---|
| 0 | 4 | Absent | - | Store 4:0 |
| 1 | 7 | Absent | - | Store 7:1 |
| 2 | 4 | 0 | 2 > 1 | Fail, update to 4:2 |
| 3 | 4 | 2 | 1 <= 1 | Return True |
219 · Correctness and cost
The latest occurrence minimizes distance to the current index. If it is too far, all older occurrences are too far. Updating preserves this property.
One lookup, distance comparison, and update per value give expected O(n) time. There are d entries for d distinct values, so auxiliary space is O(d), d<=n. Even with k=1, all-distinct input leaves n keys; this implementation is not O(k)-space.
219 · Counterexamples and checks
Keeping only the first position misses the last pair in [4,7,4,4], k=1. No distinct-index pair qualifies when k=0.
nums=[4,7,4,4], k=1 → True
Implement and execute
def nearby_duplicate(nums, k):
latest = {}
for index, value in enumerate(nums):
if value in latest and index - latest[value] <= k:
return True
latest[value] = index
return False
python trace_lab.py --case nearby_duplicate
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 167: Two Sum II - Input Array Is Sorted · Medium
Return 1-based positions of a target-sum pair in a sorted array.
2 <= n <= 30000; values/target -1000..1000; nondecreasing; one answer; constant extra space.
Predict before implementing
Start at both ends. If the sum is too large, move the right pointer left; if too small, move the left pointer right. Track sums 10 then 7. Convert zero-based positions to the required one-based answer.
two_sum_sorted([1, 4, 6, 9], 7)
# [1, 3]
Idea and state transitions
167 · Staged hints
Find two distinct positions summing to target in a nondecreasing array. Return 1-based indices using O(1) auxiliary space.
LeetCode 167: Two Sum II - Input Array Is Sorted · Medium
H1. If the endpoint sum is too small, which candidates are all too small?
H2. Does the elimination remain valid without sorting?
H3. While left<right, move left inward for a small sum and right inward for a large sum.
nums=[1,4,6,9], target=7
| Current pair | Sum | Decision for target=7 | Removed candidates |
|---|---|---|---|
| 1,9 | 10 | Too large | 9 paired with 1,4,6 |
| 1,6 | 7 | Answer | No further elimination |
167 · Correctness and cost
If the sum is small, no partner at or below right works with left. If large, no partner at or above left works with right. Each elimination preserves any answer.
The initial gap right-left is n-1 and decreases by at least one per iteration, giving O(n) comparisons. Two pointers and a sum use O(1) auxiliary space; the two returned positions use O(1). No copy or sorting step is present.
167 · Counterexamples and checks
Outside the sorted contract, [3,1,4], target=5 defeats this rule. left==right reuses one element.
numbers=[1,4,6,9], target=10 → [1,4]
Implement and execute
def two_sum_sorted(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left + 1, right + 1]
if total < target:
left += 1
else:
right -= 1
return []
python trace_lab.py --case two_sum_sorted
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 15: 3Sum · Medium
Return distinct value triplets summing to zero at three distinct positions.
3 <= n <= 3000; values -10^5..10^5.
Predict before implementing
Sort, fix one value, and find its opposite using two pointers. Skip equal fixed values and equal pointer values after a match. Try [0,0,0,0]: four indices produce only one distinct value triple.
three_sum([-2, 0, 1, 1, 2],)
# [[-2, 0, 2], [-2, 1, 1]]
Idea and state transitions
15 · Staged hints
Return all distinct value triples from three distinct positions whose sum is zero. Results contain values rather than indices, with no repeated value combination.
LeetCode 15: 3Sum · Medium
H1. What remains after fixing one value?
H2. Does fixing the same value again create a new triplet?
H3. Sort a copy, fix the first value, and use two pointers on the suffix; skip repeated fixed values and matched pair values.
nums=[-2,0,1,1,2]
| index,left,right | Values | Sum | Action |
|---|---|---|---|
| 0,1,4 | -2,0,2 | 0 | Store [-2,0,2]; move both |
| 0,2,3 | -2,1,1 | 0 | Store [-2,1,1]; move both |
| 0,3,2 | Interval ended | - | Finish fixed value -2 |
15 · Correctness and cost
Every ordered triplet is examined when its smallest value is fixed. Sorted elimination is valid; skipping duplicates removes repeated value combinations only.
There are at most n fixed positions, each with O(n) total pointer movement: O() time. Duplicate-skipping loops are part of those same movements, not another factor of n. O(n log n) sorting is dominated. Copy/sort workspace is O(n), separate from O(z) space for z output triplets.
15 · Counterexamples and checks
[0,0,0,0] yields one triplet. Equal values at distinct positions remain allowed.
nums=[-2,0,1,1,2] → [[-2,0,2],[-2,1,1]]
Implement and execute
def three_sum(nums):
values = sorted(nums)
result = []
for index in range(len(values) - 2):
if index and values[index] == values[index - 1]:
continue
left, right = index + 1, len(values) - 1
while left < right:
total = values[index] + values[left] + values[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([values[index], values[left], values[right]])
left += 1
right -= 1
while left < right and values[left] == values[left - 1]:
left += 1
while left < right and values[right] == values[right + 1]:
right -= 1
return result
python trace_lab.py --case three_sum
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.