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 longest_unique
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_02.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
Choosing state from the contract
| Problem | Stored state | Update justification | Cost |
|---|---|---|---|
| Longest unique interval | Set, left boundary | Remove repeat before insertion | Expected O(n) time |
| Shortest target interval | Sum, left boundary | Positivity and recorded lengths | O(n) time |
| Min Stack | Value and minimum per depth | Restore previous minimum | O(1) queries |
| Postfix evaluation | Stack of subexpression values | Pop right, then combine | O(t) time |
Distinguish pointer movements, set operations, and list resizing when counting work. Explain both a successful example and a counterexample that breaks an incorrect state update.
LeetCode 3: Longest Substring Without Repeating Characters · Medium
Return the maximum length of a contiguous substring without repeated characters.
0 <= n <= 10^5; letters, digits, symbols, and spaces.
Predict before implementing
Keep a left boundary and last-seen indices. A repeated character moves left to max(left, previous+1). The last a must not move left backward. Compare abba with abca.
longest_unique('abba',)
# 2
Idea and state transitions
3 · Staged hints
Return the longest substring length without repeats; spaces count, empty input gives 0.
LeetCode 3: Longest Substring Without Repeating Characters · Medium
- H1. Are all characters in the current interval distinct?
- H2. How many left moves are needed to remove a duplicate?
- H3. Remove leftmost characters until the incoming character is absent, then add it.
text="abba c"
| right, character | left before | Removed | Window after insertion | best |
|---|---|---|---|---|
| 0, a | 0 | None | a | 1 |
| 1, b | 0 | None | ab | 2 |
| 2, b | 0 | a, b | b | 2 |
| 3, a | 2 | None | ba | 2 |
| 4, space | 2 | None | ba␠ | 3 |
| 5, c | 2 | None | ba␠c | 4 |
3 · Correctness and cost
After insertion, the set represents the unique-character window. Its left boundary is the earliest feasible one for that right endpoint. Each pointer advances at most n times.
right advances n times and left at most n times without moving back. Sum their movements, at most 2n, instead of multiplying apparent loop bounds. With expected O(1) set operations, time is expected O(n). At most min(n,a) characters are retained, giving O(min(n,a)) auxiliary space for alphabet size a.
3 · Counterexamples and checks
A single removal on “abba” leaves b duplicated. Empty text gives 0; one space gives 1.
text="abba c" → 4 ("ba c")
Implement and execute
def longest_unique(text):
active, left, best = set(), 0, 0
for right, char in enumerate(text):
while char in active:
active.remove(text[left])
left += 1
active.add(char)
best = max(best, right - left + 1)
return best
python trace_lab.py --case longest_unique
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 209: Minimum Size Subarray Sum · Medium
Return the shortest contiguous interval reaching target, or zero if none exists.
1 <= n <= 10^5; 1 <= nums[i] <= 10^4; 1 <= target <= 10^9.
Predict before implementing
Extend the right end and add its value. While sum meets the target, record the length and remove the left value. At the final 3, the valid window [4,3] has length 2. Explain why positive inputs make shrinking safe.
min_subarray(7, [2, 3, 1, 2, 4, 3])
# 2
Idea and state transitions
209 · Staged hints
Return the minimum length of a contiguous subarray of positive numbers with sum at least positive target. Return zero if none exists.
LeetCode 209: Minimum Size Subarray Sum · Medium
- H1. Must every interval be summed again?
- H2. How does removing the left value change the sum?
- H3. Extend right, then record and shrink while the sum qualifies.
target=6, nums=[1,2,4,2]
| Action | Window | total | best |
|---|---|---|---|
| Add 1 and 2 | [1,2] | 3 | Not found |
| Add 4, record length | [1,2,4] | 7 | 3 |
| Remove 1, record length | [2,4] | 6 | 2 |
| Remove 2, stop shrinking | [4] | 4 | 2 |
| Add final 2, record | [4,2] | 6 | 2 |
209 · Correctness and cost
Positivity makes shrinking decrease the sum. Record each valid window before shrinking. A discarded left boundary can only produce longer later windows.
Each value is added once and removed at most once. Total boundary movement is at most 2n, giving O(n) time. No window is copied; total, left, right, and best use O(1) auxiliary space. The n-entry input is counted separately from workspace.
209 · Counterexamples and checks
Outside the positive-only contract, target=3, [1,-1,3] can make this rule miss length 1.
target=6, nums=[1,2,4,2] → 2
Implement and execute
def min_subarray(target, nums):
total = left = 0
best = len(nums) + 1
for right, value in enumerate(nums):
total += value
while total >= target:
best = min(best, right - left + 1)
total -= nums[left]
left += 1
return 0 if best > len(nums) else best
python trace_lab.py --case min_subarray
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 155: Min Stack · Medium
Implement push, pop, top, and current minimum with constant-time stack operations; explain the amortized cost of Python list updates.
Signed 32-bit values; at most 30000 calls; pop/top/getMin on nonempty stacks.
Predict before implementing
Push 2,1,1; query the minimum, pop, query, pop, query. Store the minimum so far with each value. Both copies of 1 need their own minimum record; the three queried minima are 1,1,2.
# MinStack: push(2), push(1), push(1); getMin, pop, getMin, pop, getMin
# [1, 1, 2]
Idea and state transitions
155 · Staged hints
push adds a value and pop removes the top. top returns the top value; getMin returns the minimum of all retained values. Queries and removals are called only on nonempty stacks.
LeetCode 155: Min Stack · Medium
- H1. How can the previous minimum be restored after a pop?
- H2. What happens when the minimum occurs twice?
- H3. Store (value, minimum through this depth) per entry. Create entries separately for each instance.
push(2), push(2), push(5), pop(), pop()
| Operation | Stored (value, minimum) pairs | getMin result |
|---|---|---|
| push(2) | [(2,2)] | 2 |
| push(2) | [(2,2),(2,2)] | 2 |
| push(5) | [(2,2),(2,2),(5,2)] | 2 |
| pop() | [(2,2),(2,2)] | 2 |
| pop() | [(2,2)] | 2 |
155 · Correctness and cost
Induction on depth gives the correct prefix minimum; popping the last pair restores the previous prefix minimum.
At depth d, getMin and top read one slot and cost O(1). Push and pop are amortized O(1), including list resizing. Two values per depth give 2d stored values, or O(d) space. Recomputing min over the whole stack would make each query O(d).
155 · Counterexamples and checks
Calling min over the stack costs O(d). A single current minimum loses its predecessor after a pop.
push(2),push(2),push(5),pop(),pop(),getMin() → 2
Implement and execute
class MinStack:
def __init__(self):
self.entries = []
def push(self, val):
minimum = min(val, self.entries[-1][1]) if self.entries else val
self.entries.append((val, minimum))
def pop(self):
self.entries.pop()
def top(self):
return self.entries[-1][0]
def getMin(self):
return self.entries[-1][1]
python trace_lab.py --case MinStack
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 150: Evaluate Reverse Polish Notation · Medium
Evaluate an integer expression in postfix notation, truncating division toward zero.
1..10^4 tokens; operands -200..200; +,-,*,/; valid expression, no zero divisor, signed 32-bit intermediate results.
Predict before implementing
Read tokens left to right. For an operator, pop the right operand before the left operand. Division truncates toward zero: 7 / -3 becomes -2. Compare Python floor division, which gives -3.
rpn(['7', '-3', '/'],)
# -2
Idea and state transitions
150 · Staged hints
Evaluate valid postfix string tokens. Integer division truncates toward zero; inputs never divide by zero.
LeetCode 150: Evaluate Reverse Polish Notation · Medium
- H1. Is the first popped value the left or right operand?
- H2. Which way should -5/2 be truncated?
- H3. Push numbers; pop right then left for an operator and push its result. Divide absolute integers and restore the sign.
tokens=["9","4","-","-2","/"]
| Token | Stack before | Operation | Stack after |
|---|---|---|---|
| 9 | [] | push(9) | [9] |
| 4 | [9] | push(4) | [9,4] |
| - | [9,4] | left=9, right=4 | [5] |
| -2 | [5] | push(-2) | [5,-2] |
| / | [5,-2] | 5 / -2, truncate toward zero | [-2] |
150 · Correctness and cost
The stack preserves completed subexpression values in order. Each operator combines the final two; a valid complete expression leaves one value.
Each of t tokens performs at most two pops, one append, and one arithmetic operation, giving O(t) time. The bounded 32-bit intermediates support constant-cost arithmetic. Many uncombined operands can accumulate, so peak auxiliary space is O(t), even though only one value remains at the end.
150 · Counterexamples and checks
5//-2 is -3, but truncation toward zero gives -2. Reversing operands changes subtraction.
tokens=["9","4","-","-2","/"] → -2
(left < 0) != (right < 0) tests whether the signs differ. For 5 and −2, False != True gives a negative result, −2. For −5 and −2, True != True is False, giving +2. Operator token "-" and numeric token "-2" are different strings, so the latter is converted with int.
Implement and execute
def rpn(tokens):
stack = []
for token in tokens:
if token not in {"+", "-", "*", "/"}:
stack.append(int(token))
continue
right, left = stack.pop(), stack.pop()
if token == "+":
value = left + right
elif token == "-":
value = left - right
elif token == "*":
value = left * right
else:
quotient = abs(left) // abs(right)
value = -quotient if (left < 0) != (right < 0) else quotient
stack.append(value)
return stack[0]
python trace_lab.py --case rpn
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.