Week 3 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 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

Save the successor before reversing the current link

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.