7 · Sorting, Big-O and top-k with heaps Code

sorted(key=), stability, tie-breaking · O(n log n) vs O(n log k) · heapq idioms

Why it matters for NPE. 'Return the 10 most frequent IPs' is the canonical NPE follow-up. You need to state complexity fluently and know when a heap beats a full sort.

Primer: "rank by a computed value" is one question with three answers

Every ranking problem in this round has the same shape: compute a number per item (a count, a distance, a speed), then return the items in order or return the top k. You have three tools. Sort everything, O(n log n). Keep a heap of size k, O(n log k). Bucket by the value when the value is a small integer, O(n + range). The grader is listening for which one you pick and why, said in terms of the variables they named: n lines, u distinct keys, k results.

Watch

Sorting: the API you must type without thinking

from operator import itemgetter, attrgetter

sorted(items)                       # new list, any iterable (dict keys, set, generator)
items.sort()                        # in place, returns None, lists only

sorted(words, key=len)              # key is called once per element, O(n) calls
sorted(hosts, key=str.lower)        # case-insensitive
sorted(rows, key=lambda r: r[2])    # by one field
sorted(rows, key=itemgetter(2))     # same thing, slightly faster
sorted(rows, key=itemgetter(2, 0))  # by field 2, then field 0
sorted(objs, key=attrgetter('count'))

# descending, two ways
sorted(nums, reverse=True)
sorted(nums, key=lambda x: -x)

# multi-key: count descending, then name ascending (negate the number, leave the string)
sorted(counts.items(), key=lambda kv: (-kv[1], kv[0]))

# dict by value, highest first
sorted(d.items(), key=itemgetter(1), reverse=True)
max(d, key=d.get)                   # just the one best key, O(n), no sort needed

Stability, and why tie-breaks depend on it

Python's sort is stable: items with equal keys keep their input order. Two consequences you can use in an interview.

• Chained sorts. To sort by count descending then name ascending when you cannot negate the name, sort twice: by the secondary key first, then by the primary. rows.sort(key=itemgetter(0)); rows.sort(key=itemgetter(1), reverse=True). The second sort keeps the alphabetical order inside each count group because it is stable.
• reverse=True is not "sort then reverse". It keeps equal elements in their original order. sorted(x)[::-1] would flip the ties too. This matters when the problem says "ties by first appearance".
• Negation vs reverse=True. reverse=True flips every field of a tuple key. Negating one numeric field flips only that field. Mixed directions need negation (or the chained-sort trick for strings).
• Counter.most_common() uses a stable sort, so equal counts come out in first-insertion order, not alphabetically. If the question specifies alphabetical ties you must sort with an explicit key.

Which sort runs, and when O(n log n) is not the floor

Sort Characters By Frequency is the cleanest demonstration. With a sort: ''.join(ch * c for ch, c in Counter(s).most_common()), O(n + u log u). With buckets indexed by count: O(n + u) because the count can never exceed n. Say both; type the first.

Big-O recap in the interviewer's variables

Amortised means "a single operation can be expensive, but any sequence of m operations costs O(m) total". Use the word for append, dict growth and the resize of a dynamic array. Do not use it for heap pushes; those are O(log n) every time.

Heaps with heapq

A heap is a list arranged so that heap[0] is always the smallest item. The children of index i live at 2i+1 and 2i+2. Push appends and bubbles up; pop swaps the last item into the root and sinks it down. Both are O(log n). Nothing else about the list is sorted.

import heapq

heap = []
heapq.heappush(heap, 5)             # O(log n)
smallest = heapq.heappop(heap)      # O(log n); IndexError on empty
heap[0]                             # peek, O(1)
heapq.heapify(nums)                 # in place, O(n). Do this instead of n pushes.
heapq.heappushpop(heap, x)          # push x then pop the smallest: cheaper than two calls
heapq.heapreplace(heap, x)          # pop the smallest then push x (heap size unchanged)

# max-heap: negate on the way in, negate on the way out
heapq.heappush(heap, -x)
largest = -heapq.heappop(heap)

# priorities with payloads: tuples compare field by field
heapq.heappush(heap, (priority, tiebreak, item))   # tiebreak keeps items from being compared
#   e.g. (-count, word) ranks high count first, then alphabetical

# top-k helpers: O(n log k), return a sorted list
heapq.nlargest(k, nums)
heapq.nsmallest(k, points, key=lambda p: p[0] ** 2 + p[1] ** 2)
heapq.nlargest(k, counts, key=counts.get)           # counts is a Counter: rank keys by value
heapq.nlargest(k, counts.items(), key=lambda kv: kv[1])   # (key, count) pairs

# k-way merge of sorted iterables: lazy, O(N log m) for m inputs
for line in heapq.merge(file_a, file_b, key=lambda l: int(l.split(',', 1)[0])):
    ...

nlargest and nsmallest keep a size-k heap internally while scanning, so they are O(n log k). When k is close to n they fall back to a full sort. If k is 1 use max or min; if k is n use sorted.

The size-k min-heap idiom for the k largest

Keep the k largest seen so far in a min-heap. The root is the weakest of the current winners. A new item only enters if it beats the root, and then the root leaves. After the scan the heap holds the answer and heap[0] is the kth largest.

def k_largest(nums, k):
    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)   # pop the weakest winner, push x
    return heap                           # unordered; sorted(heap, reverse=True) if order matters

O(n log k) time, O(k) space, and it works on a stream: you never need all n in memory. That last sentence is what the "huge log file" follow-up wants.

Worked examples

Top K Frequent Elements, three ways

from collections import Counter
import heapq

def top_k_sort(nums, k):                  # O(n + u log u) time, O(u) space
    counts = Counter(nums)
    return [x for x, _ in sorted(counts.items(), key=lambda kv: -kv[1])[:k]]

def top_k_heap(nums, k):                  # O(n + u log k) time, O(u + k) space
    counts = Counter(nums)
    return heapq.nlargest(k, counts, key=counts.get)

def top_k_buckets(nums, k):               # O(n + u) time, O(n) space
    counts = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]    # index = frequency; max frequency is n
    for x, c in counts.items():
        buckets[c].append(x)
    out = []
    for c in range(len(buckets) - 1, 0, -1):        # highest frequency first
        for x in buckets[c]:
            out.append(x)
            if len(out) == k:
                return out
    return out

Say: "Counting is O(n) and O(u) in all three. The ranking step is where they differ: u log u, u log k, or linear with buckets because a frequency is bounded by n." Type the heap version. Offer the buckets when asked for better. Counter.most_common(k) is the heap version in one call.

Kth Largest Element in an Array

def find_kth_largest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)                   # O(k)
    for x in nums[k:]:
        if x > heap[0]:
            heapq.heapreplace(heap, x)    # O(log k)
    return heap[0]                        # the weakest of the k strongest = kth largest

O(n log k) time, O(k) space. One-liner: heapq.nlargest(k, nums)[-1]. Sorting is O(n log n) and fine to say first. Quickselect is average O(n); mention it as the theoretical best and move on. Follow-up "the numbers arrive one at a time": wrap the heap in a class with an add(x) method; that is LC 703.

K Closest Points to Origin

def k_closest(points, k):
    heap = []                                   # max-heap on distance: the farthest kept point is at the root
    for x, y in points:
        d = x * x + y * y                       # no sqrt: monotone, so the ranking is identical
        if len(heap) < k:
            heapq.heappush(heap, (-d, x, y))
        elif d < -heap[0][0]:
            heapq.heapreplace(heap, (-d, x, y))
    return [[x, y] for _, x, y in heap]

# or: heapq.nsmallest(k, points, key=lambda p: p[0] ** 2 + p[1] ** 2)

Here you want the k smallest, so the heap keeps the k best and evicts the largest: negate the distance to make a max-heap. The x and y in the tuple break ties so two equal distances never compare lists.

Top K Frequent Words: the alphabetical tie-break trap

Output must be by count descending, then word ascending. You cannot negate a string, so nlargest with (count, word) is wrong: it would rank "z" above "a" on ties.

def top_k_words(words, k):
    counts = Counter(words)
    return heapq.nsmallest(k, counts, key=lambda w: (-counts[w], w))   # O(u log k)
    # same ordering with a sort: sorted(counts, key=lambda w: (-counts[w], w))[:k]   O(u log u)

Flip the problem: ask for the k smallest under the key (-count, word). Negative count puts high counts first; the word sorts ascending naturally. This is exactly the ordering rule in file lab 4.

Last Stone Weight: simulate with a max-heap

def last_stone_weight(stones):
    heap = [-s for s in stones]
    heapq.heapify(heap)                       # O(n)
    while len(heap) > 1:
        a = -heapq.heappop(heap)              # heaviest
        b = -heapq.heappop(heap)              # second heaviest
        if a != b:
            heapq.heappush(heap, -(a - b))
    return -heap[0] if heap else 0

Each round removes at least one stone, so at most n rounds of O(log n) work: O(n log n). The pattern "repeatedly take the two extremes, combine, put back" is always a heap. Task Scheduler is the same idea with a cooldown queue.

The 10 most frequent IPs in a huge access log

def top_ips(path, k=10):
    counts = Counter()
    with open(path, encoding='utf-8') as f:          # streams: O(1) memory per line
        for line in f:
            parts = line.split()
            if not parts:
                continue
            counts[parts[0]] += 1                      # IP is the first field in common log format
    return heapq.nlargest(k, counts.items(), key=lambda kv: kv[1])

Complexity. O(n) to scan n lines. O(u) memory for u distinct IPs. O(u log k) to rank. Not O(n log n), and not O(k) memory: the Counter is the big object.

Follow-up: the number of distinct IPs does not fit in memory. The streaming loop is already fine; the Counter is the problem. Answers in increasing order of effort:

1. Shrink the keys. An IPv4 address as a string is 40+ bytes in Python; as an int it is far less. int(ipaddress.ip_address(s)) or pack the four octets. Often enough to fit.
2. Partition by hash. One pass writes each line to one of m files chosen by hash(ip) % m. Every occurrence of an IP lands in the same file, so each file can be counted independently with a Counter that fits. Take the top k of each partition, then the top k of those m·k candidates. Exact. O(n) extra I/O, O(u/m) memory per partition.
3. External sort, then one pass. Sort the IP column in chunks, heapq.merge the chunks, count runs of equal IPs as they stream by, keep a size-k heap. O(n log n) I/O, O(k) memory for the final step.
4. Approximate. A Count-Min sketch gives frequency estimates in fixed memory; pair it with a size-k heap of candidates. Say it only if the interviewer accepts approximate answers.

Say "partition by hash" first. It is exact, it is the answer to every "distinct keys do not fit" follow-up (topic 3 duplicates, topic 5 grouping), and you can describe it in two sentences.

Interview questions

Traps

• heapq.nlargest(k, counter) without key=counter.get returns the k largest keys, not the most frequent. Same with sorted(counter).
• Pushing lists or objects and then mutating them. Changing a priority after the push silently breaks the heap invariant; pop and re-push instead.
• Building a list and forgetting heapify before the first heappop. The list is not a heap until you call it. Popping from a plain list returns the wrong item with no error.
• Claiming "O(k) memory" for a top-k over a log. The size-k heap is O(k); the Counter you built first is O(u). Say both.
• Assuming heap[1] is the second smallest, or iterating the heap expecting sorted order. Only heap[0] is guaranteed. Pop repeatedly or sorted(heap).
• reverse=True with a tuple key when only one field should be descending. It flips every field.
• Sizing frequency buckets by the number of distinct keys instead of n+1. A single key can have frequency n.
• x = nums.sort(). x is now None.

Do before marking this topic done

Blank editor, no autocomplete, tiny inputs, complexity said out loud for each.

1. Top K Frequent Elements three ways: sort, nlargest with a key, buckets. State the time of the counting step and the ranking step separately for each.
2. Top K Frequent Words with the count-descending, word-ascending rule. Then redo file lab 4 (busiest clients) from memory with the same ordering.
3. Kth Largest Element with a size-k min-heap, then wrap it in a class with add(x) that returns the current kth largest after each call (the streaming version).
4. Last Stone Weight with a negated heap. Then Sort Characters By Frequency with most_common, then with buckets.
5. Write top_ips for a log file and answer "what if distinct IPs do not fit" with the hash-partition plan. Then merge two sorted log files with heapq.merge (lab 9) and say why it is O(N log 2) and streams.

Practice: linked problems

Logged attempts feed the tracker. Open the problem in a new tab, solve in a blank editor, then log honestly.

• LC 1046Last Stone WeightEasy
• LC 347Top K Frequent ElementsMedium
• LC 451Sort Characters By FrequencyMedium
• LC 215Kth Largest Element in an ArrayMedium
• LC 692Top K Frequent WordsMedium
• LC 973K Closest Points to OriginMedium
• LC 621Task SchedulerMedium

← 6 · ARP, ICMP, DHCP, DNS and the life of a packet · all topics · 8 · TCP vs UDP: handshake, state, loss and congestion control →