Complexity, and the six patterns behind most rounds

A coding round is not a test of whether you can solve the problem. Given unlimited time, most students can. It is a test of whether you can solve it within the intended complexity, and the problem tells you what that is if you read it properly.

Read the constraints first

The input size tells you which complexities can pass. Roughly 10⁸ simple operations per second is a fair budget for Python — less than C++, which is why the intended solution matters more.

So n ≤ 10⁵ is the problem telling you "do not write a nested loop". And n ≤ 20 is the problem telling you "an exponential search is expected — stop looking for a clever formula". Read the constraints before you start thinking, not after your first attempt times out.

The notation, briefly

Big-O is an upper bound on growth as input grows, ignoring constants. O(2n + 100) is O(n), because doubling n doubles the time either way.

def f(xs):                    # O(1)      — one operation
    return xs[0]

def g(xs):                    # O(n)      — one pass
    return sum(xs)

def h(xs):                    # O(n²)     — a pass inside a pass
    return [(a, b) for a in xs for b in xs]

def k(xs):                    # O(n log n) — sort dominates
    return sorted(xs)[len(xs) // 2]

Two things people get wrong. Space complexity counts too — a solution that builds a dictionary of every element is O(n) space, and some questions forbid that. And complexity is about the dominant term: two separate loops are O(n), not O(n²); a loop inside a loop is O(n²).

The six patterns

Almost every screening-round question is one of these six, or two of them combined.

1. Two pointers

Two indices moving through a sequence, usually towards each other. Turns an O(n²) pair search into O(n) — but requires the input to be sorted, or the problem to have some order you can exploit.

def pair_sums_to(xs, target):
    """xs is sorted. Is there a pair adding to target?"""
    left, right = 0, len(xs) - 1
    while left < right:
        total = xs[left] + xs[right]
        if total == target:
            return (xs[left], xs[right])
        if total < target:
            left += 1          # need a bigger sum
        else:
            right -= 1         # need a smaller sum
    return None

print(pair_sums_to([1, 3, 4, 7, 9], 11))    # (4, 7)

Signals: sorted array, pair, triplet, palindrome, reverse in place, remove duplicates in place, merge two sorted lists.

2. Sliding window

A window over a contiguous run, expanded on the right and shrunk on the left, with a running summary so you never recompute the window from scratch.

def longest_unique(s):
    """Length of the longest substring with no repeated character."""
    seen = {}                  # char -> last index
    start = best = 0
    for i, c in enumerate(s):
        if c in seen and seen[c] >= start:
            start = seen[c] + 1        # jump the window past the repeat
        seen[c] = i
        best = max(best, i - start + 1)
    return best

print(longest_unique("abcabcbb"))     # 3

The crucial discipline: never slice the window. s[start:i] inside the loop makes it O(n²) again, which is the mistake that quietly loses marks.

Signals: substring, subarray, contiguous, longest, at most k, fixed size k.

3. Hashing

A dict or set that remembers what you have seen, so a second pass is unnecessary.

def two_sum(xs, target):
    """Unsorted. Return the indices of the pair adding to target."""
    seen = {}                              # value -> index
    for i, x in enumerate(xs):
        if target - x in seen:             # O(1)
            return (seen[target - x], i)
        seen[x] = i
    return None

print(two_sum([2, 7, 11, 15], 9))     # (0, 1)

One pass, O(n) time, O(n) space. Compare with the two-pointer version above: that one needs sorting (O(n log n)) but uses O(1) extra space. Being able to state that trade-off is often the real question.

Signals: duplicate, seen before, frequency, anagram, first non-repeating, group by.

4. Prefix sums

Precompute cumulative totals so any range sum becomes one subtraction.

from itertools import accumulate

xs = [2, 4, 1, 5, 3]
prefix = [0] + list(accumulate(xs))    # [0, 2, 6, 7, 12, 15]

def range_sum(i, j):                   # sum of xs[i:j], O(1)
    return prefix[j] - prefix[i]

print(range_sum(1, 4))                 # 4 + 1 + 5 = 10

Build once in O(n), then answer any number of range queries in O(1) each. The leading zero is what makes range_sum(0, j) work without a special case.

Signals: sum of a range, many queries, subarray sums to k, equilibrium index, count subarrays.

5. Binary search

Halve the search space each step. Two forms, and the second is the one that separates candidates.

def find(xs, target):
    """Classic: search a sorted array. O(log n)."""
    lo, hi = 0, len(xs) - 1
    while lo <= hi:
        mid = (lo + hi) // 2           # in Python there is no overflow to worry about
        if xs[mid] == target:
            return mid
        if xs[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

def min_capacity(weights, days):
    """Binary search on the ANSWER, not on the array.
    Smallest daily capacity that ships all weights within `days` days."""

    def days_needed(cap):
        days_used, load = 1, 0
        for w in weights:
            if load + w > cap:
                days_used += 1
                load = 0
            load += w
        return days_used

    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(mid) <= days:
            hi = mid                   # feasible — try smaller
        else:
            lo = mid + 1               # not feasible — need bigger
    return lo

print(min_capacity([1, 2, 3, 4, 5], 3))    # 6

The second form is the pattern to recognise: when the answer is a number in a known range, and "is X good enough?" is easy to check, binary search the answer. Signals for it are minimum maximum, maximum minimum, smallest such that, and a numeric bound like 1 ≤ answer ≤ 10⁹.

6. Recursion with memoisation

Express the answer in terms of smaller answers, then stop recomputing them.

from functools import cache

@cache
def ways(n):
    """Ways to climb n stairs taking 1 or 2 steps at a time."""
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

print(ways(40))     # 165580141, instantly

Without @cache that is O(2ⁿ). With it, each n is computed once — O(n).

The bottom-up version uses no recursion and no stack, which is what you want for large n:

def ways_iterative(n):
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

Signals: count the ways, minimum cost, can it be done, choose or skip, longest increasing/common, a grid you can only move right and down through.

Combining them

Real questions layer patterns. "Longest subarray with sum at most k" is a sliding window with a prefix sum. "K most frequent elements" is hashing with a heap. "Group anagrams" is hashing with a sorted key. When you recognise two patterns at once, you are usually right.

A method for the four minutes before you type

1. Read the constraints. They name the target complexity.
2. Restate the problem in one sentence, out loud if it is an interview. Half of all wrong answers are answers to a different question.
3. Do one small example by hand. Not in your head — on paper.
4. Name the pattern. If two fit, say both and pick one.
5. Say the complexity you are aiming for before you write it. If it is worse than the constraints allow, you have not finished thinking.
6. Write the brute force if you are stuck. A working O(n²) beats an unfinished O(n), and an interviewer will usually help you improve it.
7. Test the edges before submitting. Empty input, one element, all-equal elements, negative numbers, the maximum size.

That last line is worth more marks than any pattern on this page. The most common reason a correct approach fails a hidden test case is an empty input or a single-element input.

What to take into an interview

• The constraints tell you the intended complexity. Read them first.
• Two pointers: sorted input, pairs, in-place. O(1) space.
• Sliding window: contiguous runs. Never slice the window.
• Hashing: seen-before, frequency, duplicates. O(n) time for O(n) space.
• Prefix sums: many range queries after one O(n) pass.
• Binary search: on a sorted array, or on the answer when feasibility is checkable.
• Recursion plus @cache: overlapping subproblems. Then rewrite bottom-up if n is large.
• Always state your complexity out loud, and always test the empty and single-element cases.