Week 2 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 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.