Phase 3: Linear Management & Searching

In Phases 1 and 2 you learned to store data in lists, strings, dictionaries, stacks and queues. This phase is about managing that data efficiently: putting it in order, finding things in it fast, and answering questions about ranges of it without re-scanning everything. By the end you will be able to sort with custom rules, write a binary search that does not go wrong at the edges, and recognise the four patterns that solve most "array" interview problems: two pointers, sliding window, prefix sums and Kadane's algorithm. You will also handle intervals and walk a matrix with confidence.

Every technique here has the same goal: turn a solution that looks at every pair of elements (O(n²)) into one that looks at each element once or twice (O(n) or O(n log n)). So we start with what those symbols mean.

Big-O: why O(n log n) beats O(n²)

Big-O notation describes how the running time of an algorithm grows with the size of its input, ignoring constant factors. The ones you need this phase:

The gap between the last two is enormous. For n = 10,000, n² is 100,000,000 while n log n is about 130,000: roughly 750 times less work. For n = 1,000,000 the ratio is around 50,000. That is why "aim for O(n log n)" or "aim for O(n)" appears in problem constraints: a nested loop that is fine for 100 elements will time out on 100,000.

A quick way to estimate: a nested loop over the same list is O(n²); a single loop is O(n); anything that repeatedly halves its range is O(log n); sorting is O(n log n). If you sort once and then do a single pass, the whole thing is O(n log n) because the sort dominates.

import time

def count_pairs_slow(nums, target):
    count = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                count += 1
    return count

def count_pairs_fast(nums, target):
    seen = {}
    count = 0
    for x in nums:
        count += seen.get(target - x, 0)
        seen[x] = seen.get(x, 0) + 1
    return count

nums = list(range(3000))
for f in (count_pairs_slow, count_pairs_fast):
    t = time.perf_counter()
    f(nums, 3000)
    print(f.__name__, "took about", round((time.perf_counter() - t) * 1000), "ms")

On a typical laptop the output looks like:

count_pairs_slow took about 100 ms
count_pairs_fast took about 1 ms

Same answer, about a hundred times faster, and the gap only widens as n grows.

Sorting

The built-in sort

Python's sorted() returns a new list; list.sort() sorts in place and returns None. Both are O(n log n) and both take a key function that says what to compare.

words = ["pear", "Fig", "banana", "kiwi"]
print(sorted(words))                       # capital letters sort first
print(sorted(words, key=str.lower))        # case-insensitive
print(sorted(words, key=len))              # by length, ties keep original order
print(sorted(words, key=len, reverse=True))

['Fig', 'banana', 'kiwi', 'pear']
['banana', 'Fig', 'kiwi', 'pear']
['Fig', 'pear', 'kiwi', 'banana']
['banana', 'pear', 'kiwi', 'Fig']

Python's sort is stable: elements that compare equal keep their original relative order. That is why "pear" stays ahead of "kiwi" when sorting by length.

To sort by several fields, return a tuple from the key. Tuples compare element by element, so (age, name) means "by age, and among equal ages by name".

people = [("Bob", 30), ("Alice", 25), ("Carol", 30)]
print(sorted(people, key=lambda p: (p[1], p[0])))
# descending age, ascending name: negate the numeric field
print(sorted(people, key=lambda p: (-p[1], p[0])))

[('Alice', 25), ('Bob', 30), ('Carol', 30)]
[('Bob', 30), ('Carol', 30), ('Alice', 25)]

Common mistakes

• nums = nums.sort() sets nums to None. Use nums.sort() alone or nums = sorted(nums).
• Sorting a list of lists without a key sorts by the first element, then the second, which is sometimes what you want and sometimes a silent bug.
• You cannot negate a string to reverse only that field. Use reverse=True if every field goes the same direction, or sort twice (stable sorts make this work: sort by the secondary key first, then by the primary).

Practice: Sort People by Age, Then Name

How merge sort works

You will almost always call the built-in sort, but you should know how an O(n log n) sort works, and merge sort is the clearest. The idea is divide and conquer:

1. A list with 0 or 1 elements is already sorted.
2. Otherwise split the list in half, sort each half (recursively), and merge the two sorted halves.

Merging is the important step. Two sorted lists can be combined in one pass by keeping an index into each, repeatedly appending whichever front element is smaller:

def merge(a, b):
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:])   # only one of these is non-empty
    out.extend(b[j:])
    return out

def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    return merge(merge_sort(nums[:mid]), merge_sort(nums[mid:]))

print(merge([1, 4, 9], [2, 3, 10]))
print(merge_sort([5, 2, 4, 6, 1, 3]))

[1, 2, 3, 4, 9, 10]
[1, 2, 3, 4, 5, 6]

Why O(n log n)? Halving repeatedly produces log n levels of splitting, and at every level the merges together touch every element once, which is O(n) per level.

Practice: Merge Two Sorted Lists, Implement Merge Sort

Binary search

If a list is sorted, comparing the target with the middle element tells you which half it must be in. Discard the other half and repeat. Each step halves the range, so a million elements need only about 20 steps.

The template

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1        # inclusive bounds
    while lo <= hi:                  # range is non-empty
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1             # target is strictly to the right
        else:
            hi = mid - 1             # target is strictly to the left
    return -1

print(binary_search([1, 3, 5, 7, 9, 11], 7))
print(binary_search([1, 3, 5, 7, 9, 11], 4))

3
-1

Off-by-one pitfalls

Nearly every binary search bug is one of these:

• hi = len(nums) with while lo <= hi. Then mid can equal len(nums) and you get an IndexError. Decide up front whether hi is inclusive (len(nums) - 1, loop while lo <= hi) or exclusive (len(nums), loop while lo < hi) and stay consistent.
• lo = mid or hi = mid in the inclusive template. When lo and hi are one apart, mid equals lo, and lo = mid changes nothing: an infinite loop. In the inclusive template always move past mid (mid + 1 or mid - 1).
• Returning lo without checking. When the loop ends, lo is where the target would be inserted, which is useful (see below) but is not proof that the target is present.

Finding a boundary (lower bound)

Plain binary search stops at any match. With duplicates, you often want the first index whose value is >= target. This variant uses an exclusive hi and never skips mid, because mid itself might be the answer:

def lower_bound(nums, target):
    lo, hi = 0, len(nums)            # hi is exclusive
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid                 # mid could be the answer; keep it
    return lo

nums = [1, 2, 4, 4, 4, 7]
print(lower_bound(nums, 4))   # first 4
print(lower_bound(nums, 5))   # where 5 would be inserted
print(lower_bound(nums, 9))   # len(nums): past the end

2
5
6

Note it does not loop forever: when lo < hi, mid is strictly less than hi, so hi = mid always shrinks the range. lower_bound answers the "search insert position" problem directly, and the standard library ships it as bisect.bisect_left(nums, target). The last occurrence of a value is lower_bound(nums, target + 1) - 1.

Binary search on the answer

Sometimes there is no list at all, just a range of candidate answers where some check is false up to a point and true afterwards. Integer square root is the classic example: find the largest k with k * k <= n.

def isqrt(n):
    lo, hi = 0, n
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= n:
            lo = mid + 1             # mid works; try bigger
        else:
            hi = mid - 1
    return hi                        # last value that worked

print([isqrt(x) for x in (0, 1, 8, 9, 10, 99, 100)])

[0, 1, 2, 3, 3, 9, 10]

The same shape solves "minimum speed to finish in time", "smallest capacity to ship in d days" and many others: if you can write an is_ok(mid) check that flips from false to true exactly once, binary search finds the flip point.

Practice: Binary Search, First and Last Position of a Target, Search in Rotated Sorted Array

Two pointers

Two pointers means walking a list with two indices instead of one, so that a problem about pairs of elements is solved in a single pass rather than a nested loop. There are two flavours.

Opposite ends, moving inward

Used on sorted input, or when the answer depends on the width between the pointers. Start with left = 0, right = len - 1 and, at each step, decide which pointer to move based on the current pair.

def two_sum_sorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left, right]
        if s < target:
            left += 1        # need a bigger sum: only moving left helps
        else:
            right -= 1       # need a smaller sum
    return None

print(two_sum_sorted([1, 3, 4, 6, 8, 11], 10))

[2, 3]

The justification matters: because the list is sorted, if the sum is too small then every pair using the current left is also too small (the current right is the largest partner available), so left can safely move on. The same style of argument drives Container With Most Water, where you always move the shorter line because the taller one cannot improve the result.

Same direction (read / write)

Here both pointers move rightwards: one reads, one writes. This is how you modify a list in place without allocating a new one. Removing duplicates from a sorted list:

def remove_duplicates(nums):
    if not nums:
        return 0
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write            # number of unique elements

nums = [1, 1, 2, 3, 3, 3, 4]
k = remove_duplicates(nums)
print(k, nums[:k])

4 [1, 2, 3, 4]

Merging two sorted lists (from the sorting section) is the same idea with one reader on each input.

Common mistakes

• Using while left <= right when the two pointers must refer to different elements (it lets left == right, pairing an element with itself).
• Forgetting to skip duplicates in 3Sum, producing the same triplet twice. After finding a match, advance left while nums[left] == nums[left - 1].

Practice: Two Sum on a Sorted List, Container With Most Water, 3Sum

Sliding window

A sliding window is a two-pointer variant for contiguous subarrays or substrings. The window is nums[left:right+1]; you move right to grow it and left to shrink it, keeping some summary of the contents (a sum, a count, a set) updated in O(1) rather than recomputed.

Fixed size

When the window is always k wide, each move adds one element and drops one:

def max_sum_window(nums, k):
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]   # enters, leaves
        best = max(best, window)
    return best

print(max_sum_window([2, 1, 5, 1, 3, 2], 3))

9

Variable size

When the window must satisfy a rule (no repeated characters, sum at most s, at most two distinct values), expand right every iteration and shrink from left only as long as the rule is broken:

def longest_unique(s):
    seen = set()
    left = best = 0
    for right, ch in enumerate(s):
        while ch in seen:            # rule broken: shrink until fixed
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

print(longest_unique("abcabcbb"), longest_unique("pwwkew"))

3 3

Some problems flip the direction: the window is valid once it is big enough, and you want the shortest valid one. Then you shrink while the window is still valid, recording the length each time. Minimum size subarray with sum at least target (positive numbers only):

def min_subarray_len(target, nums):
    best = float("inf")
    left = window = 0
    for right, x in enumerate(nums):
        window += x
        while window >= target:          # valid: try to make it shorter
            best = min(best, right - left + 1)
            window -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

print(min_subarray_len(7, [2, 3, 1, 2, 4, 3]))

2

Both are O(n) because left and right each move at most n times in total, even though there is a loop inside a loop.

Common mistakes

• Moving left backwards. The window only ever slides right; if you "reset" left to an earlier position you lose the O(n) guarantee and usually the correctness too.
• Sliding windows need a monotonic quantity. With negative numbers, adding an element can make the sum go down, so "shrink while sum >= target" breaks. That is where prefix sums come in.

Practice: Maximum Sum Subarray of Size K, Longest Substring Without Repeating Characters

Prefix sums

A prefix-sum array stores running totals: prefix[i] is the sum of the first i elements, with prefix[0] = 0. Build it once in O(n) and any range sum becomes a subtraction:

nums = [3, 1, 4, 1, 5, 9]
prefix = [0]
for x in nums:
    prefix.append(prefix[-1] + x)
print(prefix)

def range_sum(left, right):          # inclusive
    return prefix[right + 1] - prefix[left]

print(range_sum(1, 3), sum(nums[1:4]))
print(range_sum(0, 5), sum(nums))

[0, 3, 4, 8, 9, 14, 23]
6 6
23 23

The leading 0 is what makes range_sum(0, r) work without a special case; the array has one more entry than nums.

Prefix sums plus a hash map

"How many subarrays sum to k?" is a pairs question in disguise: nums[i..j] sums to k exactly when prefix[j+1] - prefix[i] == k. Walking left to right with a running sum, you want to know how many earlier prefix sums equal running - k, which a Counter answers in O(1). This works with negative numbers, which the sliding window could not handle.

from collections import Counter

def subarray_sum(nums, k):
    seen = Counter({0: 1})           # the empty prefix
    running = count = 0
    for x in nums:
        running += x
        count += seen[running - k]   # look up first...
        seen[running] += 1           # ...then record
    return count

print(subarray_sum([1, 2, 3], 3), subarray_sum([1, -1, 0], 0))

2 3

Common mistakes

• Recording running before looking up running - k when k == 0: that counts the empty subarray at every position.
• Forgetting {0: 1}, which drops every subarray that starts at index 0.

Practice: Range Sum Queries, Subarray Sum Equals K

Kadane's algorithm

"Find the contiguous subarray with the largest sum" has O(n²) subarrays, but the best subarray ending at position i is easy to describe: either nums[i] alone, or nums[i] extended from the best subarray ending at i - 1. Whenever the running total would drag nums[i] down, start fresh.

def max_subarray(nums):
    current = best = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)   # extend or restart
        best = max(best, current)
    return best

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print(max_subarray([-3, -1, -2]))

6
-1

This is your first taste of dynamic programming: each step reuses the answer to a smaller version of the same question. Two things to notice. best is tracked separately because current can drop after the maximum has been seen. And initialising both to nums[0] rather than 0 is what makes an all-negative input return the least-bad element instead of 0. If you need the subarray itself, remember the index where current was last restarted.

Practice: Maximum Subarray (Kadane's Algorithm)

Intervals

Interval problems (meeting rooms, merging bookings, inserting a new range) share one first move: sort by start. Once sorted, an interval can only overlap the interval placed just before it in the output, so a single pass with a comparison against merged[-1] is enough.

def merge_intervals(intervals):
    merged = []
    for start, end in sorted(intervals):
        if merged and start <= merged[-1][1]:       # overlaps the last one
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

print(merge_intervals([[8, 10], [1, 3], [2, 6], [15, 18]]))
print(merge_intervals([[1, 4], [4, 5], [2, 3]]))

[[1, 6], [8, 10], [15, 18]]
[[1, 5]]

Two intervals [a, b] and [c, d] (with a <= c) overlap when c <= b. Use max when extending, because the new interval might end before the current merged one does ([1, 10] followed by [2, 3]). Whether touching intervals like [1, 4] and [4, 5] count as overlapping is a problem-specific rule; read the statement.

Practice: Merge Intervals

Matrices: keeping bounds straight

Matrix traversal problems (spiral order, rotate image, set zeroes) are rarely about a clever algorithm. They are about tracking boundaries carefully. For a spiral, keep top, bottom, left, right, walk each edge with a range(), and shrink the boundary you just walked. The subtle part is the last lap: once the unvisited region is a single row or column, the "bottom row" walk would repeat the "top row" walk unless you check top <= bottom again before doing it.

Two idioms worth memorising: range(right, left - 1, -1) walks leftwards inclusive of left, and list(zip(*matrix)) transposes a matrix, which combined with reversing each row rotates it 90 degrees clockwise.

matrix = [[1, 2, 3], [4, 5, 6]]
print([list(row) for row in zip(*matrix)])
print([list(row)[::-1] for row in zip(*matrix)])

[[1, 4], [2, 5], [3, 6]]
[[4, 1], [5, 2], [6, 3]]

Practice: Spiral Matrix

Checklist

Before moving to Phase 4, make sure you can do each of these without looking anything up:

• Explain why an O(n log n) algorithm beats an O(n²) one, and estimate which one a piece of code is by counting nested loops.
• Sort a list of records by two fields using sorted() with a tuple key, including one field descending.
• Describe how merge sort splits and merges, and write the merge step with two pointers.
• Write binary search from memory with inclusive bounds, and say why lo = mid + 1 (not lo = mid) is required.
• Write the lower-bound variant and use it to find the first and last occurrence of a value.
• Apply binary search to a rotated sorted array by identifying which half is sorted.
• Recognise when two pointers from opposite ends apply, and justify which pointer to move.
• Slide a fixed-size window by adding the entering element and subtracting the leaving one.
• Grow and shrink a variable-size window while maintaining a set or count of its contents.
• Build a prefix-sum array with a leading 0 and answer a range sum in O(1).
• Count subarrays with a given sum using prefix sums and a hash map, including negative numbers.
• State Kadane's recurrence (current = max(x, current + x)) and handle all-negative input.
• Merge overlapping intervals after sorting by start.
• Walk a matrix in spiral order without visiting any cell twice.