Week 1 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 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(n2)
deque popleft O(1) n calls O(n)
Search earlier list per value Up to O(n) n calls O(n2)
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(n2) 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(n2) 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 |i−j| 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(n2) 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.