SyntaxPilot
Courses/Python Coding Questions/Lesson 7
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python Coding Questions · Lesson 7 of 30

List questions III

find the missing number 1..n (sum and XOR)frequency of each element (dict, collections.Counter)majority element (Boyer-Moore voting)

These are the notes for Python Coding Questions, episode 7, our third round of list questions. Three questions that look easy: the missing number from 1 to n, the frequency of each element, and the majority element. Each starts with an answer that looks fine and then breaks: an off-by-one range, a KeyError, a sorting trick that invents a winner. Along the way we meet Gauss's sum formula, the XOR trick, collections.Counter, and Boyer-Moore voting, one of the most elegant tricks in interviews.

Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real; timings depend on the machine, so compare them, don't copy them.

Q1: The missing number from 1 to n

Real-life example: a teacher has roll numbers 1 to 5 and collects exam slips: 1, 2, 4, 5. Who is absent? She could check every roll number one by one (fine for five students, painful for a thousand), or add the slips: 1 + 2 + 3 + 4 + 5 should be 15, the slips total 12, and 15 − 12 = 3.

The list has the numbers 1 to n with exactly one missing, in any order, so it has n − 1 items: n = len(nums) + 1.

Input Output
[1, 2, 4, 5] 3
[2, 3, 1, 5, 6] 4
[1, 2, 3, 4] (the last one is missing) 5
[2] 1
[] (n = 1) 1

Attempt 1: check every roll number

def missing(nums):
    for i in range(1, len(nums)):
        if i not in nums:
            return i

print(missing([1, 2, 4, 5]))       # roll number 3 is absent
print(missing([2, 3, 1, 5, 6]))    # 4 is absent
print(missing([1, 2, 3, 4]))       # 5 is absent

Output:

3
4
None

Why it's wrong: range(a, b) stops before b. For [1, 2, 3, 4], len(nums) is 4, so the loop checks only 1, 2, 3, finds them all, and falls off the end of the function, which returns None. The missing number can be as big as n = len(nums) + 1, so the loop must run to len(nums) + 2. This is the classic off-by-one error: the last student vanished. Always test the last possible answer.

Attempt 2: fix the range, then time it

import time

def missing(nums):
    for i in range(1, len(nums) + 2):
        if i not in nums:
            return i

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

n = 30_000
nums = list(range(1, n + 1))
nums.remove(17_000)
start = time.perf_counter()
print(missing(nums), f"{time.perf_counter() - start:.3f} s")

Output (one run):

3 4 5
17000 0.596 s

Why it's still bad: the answers are right, but i not in nums on a list scans it from the start every time. 17,000 checks, each scanning up to 30,000 items: that is O(n²) time. More than half a second for 30,000 students, and 100 times more students would take about 10,000 times longer. The teacher who adds the slips does one pass.

Attempt 3: Gauss's sum formula (with /)

The sum 1 + 2 + … + n is n(n + 1) / 2 (the formula young Gauss is said to have found by pairing 1 + n, 2 + (n − 1), and so on). Subtract the sum of the list and what is left is the missing number.

def missing(nums):
    n = len(nums) + 1
    return n * (n + 1) / 2 - sum(nums)

print(missing([1, 2, 4, 5]), missing([1, 2, 3, 4]))

Output:

3.0 5.0

Why it's wrong: the numbers are right but they are floats. A roll number is never 3.0. In Python 3, a single slash / is true division and always gives a float, even when it divides exactly. Double slash // is floor division, and keeps integers as integers. Since n(n + 1) is always even (one of two neighbours is even), // is exact here.

For example 7 / 2 is 3.5, 6 / 2 is 3.0 (a float), 7 // 2 is 3. // rounds down (towards minus infinity), so -7 // 2 is −4, not −3; for our positive sums that doesn't matter.

The XOR trick

^ is XOR (exclusive or), a bitwise operator: it compares two numbers bit by bit, and each result bit is 1 when the two bits are different.

bit 2 bit 1 bit 0 value
3 0 1 1 3
5 1 0 1 5
3 ^ 5 1 1 0 6

Two rules matter:

  • x ^ x == 0: a number cancels itself.
  • x ^ 0 == x: zero changes nothing.

XOR is also order-free (a ^ b == b ^ a), so XOR all numbers from 1 to n, then XOR all numbers in the list: every present number appears twice and cancels, and only the missing one survives: (1^2^3^4^5) ^ (1^2^4^5) = 3.

Careful: 2 ^ 3 is 1, not 8. Power is **.

Why bother, if the sum works? In languages like C or Java, the sum of 1 to a big n can overflow the integer type (go past its largest value and wrap around to a wrong number). Python integers never overflow, but interviewers love this trick because an XOR result never has more bits than the numbers themselves.

The fix: both versions, every test case

import time

def missing_sum(nums):
    n = len(nums) + 1
    return n * (n + 1) // 2 - sum(nums)

def missing_xor(nums):
    x = 0
    for i in range(1, len(nums) + 2):
        x ^= i
    for v in nums:
        x ^= v
    return x

for nums in [[1, 2, 4, 5], [2, 3, 1, 5, 6], [1, 2, 3, 4], [2], []]:
    print(nums, missing_sum(nums), missing_xor(nums))

print(5 ^ 5, 5 ^ 0, 3 ^ 5 ^ 3)

n = 30_000
nums = list(range(1, n + 1))
nums.remove(17_000)
start = time.perf_counter()
print(missing_sum(nums), f"{time.perf_counter() - start:.4f} s")

Output (one run):

[1, 2, 4, 5] 3 3
[2, 3, 1, 5, 6] 4 4
[1, 2, 3, 4] 5 5
[2] 1 1
[] 1 1
0 5 5
17000 0.0001 s

Why it works: both agree on every case, including the last number (5), a list with only roll number 2 (missing 1), and the empty list (n is 1, so the missing number is 1). The 30,000-student register now takes a fraction of a millisecond instead of over half a second.

  • missing_sum: one pass (sum), O(n) time, O(1) space.
  • missing_xor: two passes, still O(n) time, O(1) space.
  • Both assume the input really is 1..n with exactly one missing. With duplicates or values outside 1..n, both give wrong answers silently; ask the interviewer.

Q2: The frequency of each element

Real-life example: a class votes for its monitor on slips. The teacher reads each slip and either writes a new name on the blackboard or adds a tally mark next to it. At the end she reads out the top two.

Input Output
["Asha", "Ravi", "Asha", "Neha", "Asha", "Ravi"] {'Asha': 3, 'Ravi': 2, 'Neha': 1}
[] {}

Attempt 1: counts[name] += 1

votes = ["Asha", "Ravi", "Asha", "Neha", "Asha", "Ravi"]
counts = {}
for name in votes:
    counts[name] += 1
print(counts)

Output:

Traceback (most recent call last):
  File "main.py", line 4, in <module>
    counts[name] += 1
    ~~~~~~^^^^^^
KeyError: 'Asha'

Why it's wrong: counts[name] += 1 means read the old value, add one, write it back. The first time Asha appears there is no old value to read, so reading a missing key raises KeyError: 'Asha', on the very first vote. The teacher can't add a tally next to a name that isn't on the board yet.

Attempt 2: dict.get, and list.count in a comprehension

counts.get(name, 0) returns the value if the key exists, otherwise the default 0. A second popular answer is a dictionary comprehension with list.count.

import time, random

votes = ["Asha", "Ravi", "Asha", "Neha", "Asha", "Ravi"]
counts = {}
for name in votes:
    counts[name] = counts.get(name, 0) + 1
print(counts)

print({x: votes.count(x) for x in votes})

random.seed(3)
big = [random.randint(1, 5_000) for _ in range(15_000)]
start = time.perf_counter()
slow = {x: big.count(x) for x in big}
print("count():", f"{time.perf_counter() - start:.3f} s")

Output (one run):

{'Asha': 3, 'Ravi': 2, 'Neha': 1}
{'Asha': 3, 'Ravi': 2, 'Neha': 1}
count(): 1.373 s

Why the .get loop works: one pass, one dictionary update per item: O(n) time, O(k) space, where k is the number of different values. Dictionaries keep insertion order, so names appear in the order they were first seen.

Why the count() version is bad: it is correct, but votes.count(x) scans the whole list, and it is called once for every item (even repeated ones: Asha is counted three times). n scans of n items: O(n²) again, more than a second for just 15,000 items.

The fix: collections.Counter

Counter (from the standard collections module) is the built-in tally sheet: it counts everything in one pass, written in C.

from collections import Counter
start = time.perf_counter()
fast = Counter(big)
print("Counter:", f"{time.perf_counter() - start:.4f} s", slow == fast)

Added to the end of the previous program, output (one run):

{'Asha': 3, 'Ravi': 2, 'Neha': 1}
{'Asha': 3, 'Ravi': 2, 'Neha': 1}
count(): 1.359 s
Counter: 0.0006 s True

About a thousandth of a second, and True: a Counter compares equal to a plain dict with the same counts. Over a thousand times faster than the count() comprehension on this machine; your numbers will differ, the gap won't.

What else Counter can do

A Counter is a dictionary with superpowers:

from collections import Counter

votes = ["Asha", "Ravi", "Asha", "Neha", "Asha", "Ravi"]
c = Counter(votes)
print(c)
print(c["Asha"], c["Zoya"])          # missing key: 0, no KeyError
print(c.most_common(2))
c.update(["Neha", "Neha"])           # two late votes
print(c.most_common())

Output:

Counter({'Asha': 3, 'Ravi': 2, 'Neha': 1})
3 0
[('Asha', 3), ('Ravi', 2)]
[('Asha', 3), ('Neha', 3), ('Ravi', 2)]
  • Missing key gives 0: c["Zoya"] is 0, not a KeyError (and reading it does not add Zoya to the Counter).
  • most_common(k) returns the top k (value, count) pairs, highest first; with no argument, all of them.
  • update(iterable) adds counts (it does not replace them like dict.update): Neha goes from 1 to 3.
  • Tie order: Neha now ties Asha with 3. When counts tie, most_common keeps them in the order they were first seen (Asha voted before Neha).

In an interview, write the .get loop to show you understand it, then say you'd use Counter in real code. Both are O(n) time, O(k) space.

Q3: The majority element

Real-life example: a housing society with 7 flats elects a secretary. The votes are 2, 2, 1, 1, 2, 2, 3. A majority means more than half the votes: more than n // 2. Candidate 2 has 4 of 7, a majority. With votes 1, 2, 3, nobody has more than half, and a good answer must say no majority.

Input Output
[2, 2, 1, 1, 2, 2, 3] 2
[3, 3, 4, 2, 3] 3
[1, 2, 3] None
[1, 1, 2, 2] (a tie: exactly half is not more than half) None
[7] 7
[] None

Attempt 1: sort and take the middle

If one value fills more than half the list, after sorting it must cover the middle position.

def majority(nums):
    return sorted(nums)[len(nums) // 2]

print(majority([2, 2, 1, 1, 2, 2, 3]))   # 2 has 4 of 7 votes
print(majority([1, 2, 3]))               # nobody has more than half
print(majority([1, 1, 2, 2]))            # a tie

Output:

2
2
2

Why it's wrong: the middle trick assumes a majority exists. Without one, the middle element is just some value: 2 "won" an election where it got one vote of three, and a tie. Also, sorting is O(n log n) time and sorted() builds a new list, O(n) space (and [] would raise IndexError). A Counter would give the right answer in O(n) time, but O(n) space. Can we do O(1) space?

Boyer-Moore voting

Named after Robert Boyer and J Strother Moore, who found it. Picture a fight between supporters:

  • Keep one candidate and a count.
  • A vote for the candidate: count + 1. A vote for anyone else: count − 1 (the two votes cancel).
  • When the count hits 0, the next vote becomes the new candidate.

Why it works: every vote for someone else can knock out at most one vote for the majority. A majority has more than half the votes, so it can never be fully cancelled: it's the one left standing.

The trace

nums = [2, 2, 1, 1, 2, 2, 3]
candidate, count = None, 0
for x in nums:
    if count == 0:
        candidate = x            # a new leader
    count += 1 if x == candidate else -1
    print(f"x={x}  candidate={candidate}  count={count}")

Output:

x=2  candidate=2  count=1
x=2  candidate=2  count=2
x=1  candidate=2  count=1
x=1  candidate=2  count=0
x=2  candidate=2  count=1
x=2  candidate=2  count=2
x=3  candidate=2  count=1
Vote x Count before What happens Candidate Count after
2 0 count was 0: 2 becomes candidate, +1 2 1
2 1 same as candidate, +1 2 2
1 2 different, −1 2 1
1 1 different, −1 2 0
2 0 count was 0: 2 takes over again, +1 2 1
2 1 same, +1 2 2
3 2 different, −1 2 1

The count goes 1 2 1 0 1 2 1, and candidate 2 is left standing. count += 1 if x == candidate else -1 uses a conditional expression: a if condition else b.

Attempt 2: voting without a check

def majority(nums):
    candidate, count = None, 0
    for x in nums:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    return candidate

for nums in [[2, 2, 1, 1, 2, 2, 3], [3, 3, 4, 2, 3], [1, 2, 3], [1, 1, 2, 2]]:
    print(nums, "->", majority(nums))

Output:

[2, 2, 1, 1, 2, 2, 3] -> 2
[3, 3, 4, 2, 3] -> 3
[1, 2, 3] -> 3
[1, 1, 2, 2] -> 1

Why it's wrong: voting always ends with some candidate. It only promises: if a majority exists, this is it. For [1, 2, 3], 1 and 2 cancel and 3 is left; for the tie, the 1s and 2s cancel at the end but 1 was the last candidate set. Voting finds a candidate, not a winner.

The fix: a verify pass

def majority(nums):
    candidate, count = None, 0
    for x in nums:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    if nums.count(candidate) > len(nums) // 2:   # second pass: check
        return candidate
    return None

for nums in [[2, 2, 1, 1, 2, 2, 3], [3, 3, 4, 2, 3], [1, 2, 3],
             [1, 1, 2, 2], [7], []]:
    print(nums, "->", majority(nums))

Output:

[2, 2, 1, 1, 2, 2, 3] -> 2
[3, 3, 4, 2, 3] -> 3
[1, 2, 3] -> None
[1, 1, 2, 2] -> None
[7] -> 7
[] -> None

Why it works: the verify pass counts the candidate's real votes and checks for more than half. For the empty list the candidate stays None, [].count(None) is 0, and 0 > 0 is False, so it returns None without a special case.

  • Two passes, each O(n): O(n) time. Just two variables: O(1) space.
  • One nums.count() call after the loop is fine; it's count() inside a loop that is O(n²).
  • If the interviewer promises a majority always exists, you may skip the second pass. Ask first: that one question shows you've thought about the edge case.

Common mistakes (and what you really see)

Mistake What you see Why Fix
range(1, len(nums)) [1, 2, 3, 4] gives None n is len + 1; range stops before its end range(1, len(nums) + 2)
if i not in nums inside a loop ~0.6 s for 30,000 numbers in on a list scans it: O(n²) sum formula or XOR, O(n)
n * (n + 1) / 2 3.0 instead of 3 / always gives a float // floor division
2 ^ 3 as a power 1, not 8 ^ is XOR 2 ** 3
counts[x] += 1 on an empty dict KeyError: 'Asha' no old value to read yet counts.get(x, 0) + 1, or Counter
{x: nums.count(x) for x in nums} over a second for 15,000 items n scans of n items: O(n²) Counter(nums)
max(counts) for the winner Zoya instead of Asha max of a dict compares keys max(counts, key=counts.get) or most_common(1)
sorted(nums)[n // 2] [1, 2, 3] gives 2 assumes a majority exists voting + verify
voting without a check [1, 2, 3] gives 3 a candidate isn't a winner second pass: count > n // 2

Your turn: the duplicate number (solution)

The mirror image of Q1: n + 1 numbers from 1 to n, so exactly one value repeats. [1, 3, 4, 2, 2] → 2, [3, 1, 3, 4, 2] → 3.

Solution

Seen set: remember every value; the first one already in the set is the duplicate. Set lookup is O(1) on average, so this is O(n) time, O(n) space. Sum formula: all of 1..n are present plus one extra, so the sum of the list minus n(n + 1) // 2 is the extra value. Here n = len(nums) − 1. O(n) time, O(1) space.

def duplicate_seen(nums):
    seen = set()
    for x in nums:
        if x in seen:              # set lookup: O(1) on average
            return x
        seen.add(x)
    return None

def duplicate_sum(nums):
    n = len(nums) - 1              # n + 1 numbers, values 1..n
    return sum(nums) - n * (n + 1) // 2

for nums in [[1, 3, 4, 2, 2], [3, 1, 3, 4, 2], [1, 1], [2, 1, 2]]:
    print(nums, duplicate_seen(nums), duplicate_sum(nums))

Output:

[1, 3, 4, 2, 2] 2 2
[3, 1, 3, 4, 2] 3 3
[1, 1] 1 1
[2, 1, 2] 2 2

Careful: the sum version only works when the duplicate appears exactly twice and every other number appears once. If a value can repeat more times ([2, 2, 2]: 2 three times, 1 absent), some numbers are missing and the sum version returns 3 while the seen set still returns 2.

Practice questions (with solutions)

1. Two missing numbers. The numbers 1 to n with two missing: [1, 3, 5, 6] → 2 and 4.

Solution

The sum formula gives a + b. The smaller missing number is at most half of that, so take pivot = (a + b) // 2 and run the sum formula again on only the values <= pivot: that gives a. O(n) time, O(1) space. (A set version, [i for i in range(1, len(nums) + 3) if i not in present], is easier to read but uses O(n) space.)

def two_missing(nums):
    n = len(nums) + 2
    total = n * (n + 1) // 2 - sum(nums)       # a + b
    pivot = total // 2                          # a <= pivot < b
    small = pivot * (pivot + 1) // 2 - sum(x for x in nums if x <= pivot)
    return small, total - small

for nums in [[1, 3, 5, 6], [2, 3, 4], [1, 2, 3, 4], []]:
    print(nums, two_missing(nums))

Output:

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

2. Elements appearing more than n/3 times. At most two values can do this.

Solution

Boyer-Moore with two candidates: a vote for neither cancels one vote of each. Then verify both. O(n) time, O(1) space. The Counter version is O(n) time, O(k) space.

from collections import Counter

def more_than_third(nums):
    c1, c2, n1, n2 = None, None, 0, 0
    for x in nums:
        if x == c1:
            n1 += 1
        elif x == c2:
            n2 += 1
        elif n1 == 0:
            c1, n1 = x, 1
        elif n2 == 0:
            c2, n2 = x, 1
        else:
            n1 -= 1
            n2 -= 1
    limit = len(nums) // 3
    return [c for c in (c1, c2) if c is not None and nums.count(c) > limit]

def more_than_third_counter(nums):
    return [x for x, k in Counter(nums).items() if k > len(nums) // 3]

for nums in [[3, 2, 3], [1, 1, 1, 3, 3, 2, 2, 2], [1, 2, 3], [1, 2], []]:
    print(nums, more_than_third(nums), more_than_third_counter(nums))

Output:

[3, 2, 3] [3] [3]
[1, 1, 1, 3, 3, 2, 2, 2] [1, 2] [1, 2]
[1, 2, 3] [] []
[1, 2] [1, 2] [1, 2]
[] [] []

3. The top 3 words in a sentence.

Solution

Lower-case it (so "The" and "the" are the same word), remove the comma, split on spaces, count.

from collections import Counter

sentence = "The chai is hot, the samosa is hot and the rain is cold"
words = sentence.lower().replace(",", "").split()
print(Counter(words).most_common(3))

Output:

[('the', 3), ('is', 3), ('hot', 2)]

"the" and "is" tie with 3; "the" comes first because it was seen first.

Quick quiz

What does this print?

from collections import Counter
c = Counter("banana")
a, z = c["a"], c["z"]
print(a, z, 7 // 2, 7 / 2, 6 ^ 6)

(A) 3 0 3 3.5 0 (B) 3 KeyError (C) 3 0 3.5 3.5 36 (D) 2 0 3 3.5 0

Answer

(A). Counter("banana") counts letters: "a" appears 3 times. A missing key in a Counter is 0, not a KeyError. 7 // 2 is floor division, 3; 7 / 2 is 3.5. A number XOR itself is 0 (^ is XOR, not a power).

3 0 3 3.5 0

Interview questions

  1. Missing number from 1 to n in O(1) space? n = len(nums) + 1, then n * (n + 1) // 2 - sum(nums), or XOR 1..n with all elements. O(n) time.
  2. Why is i not in nums in a loop slow? in on a list is a linear scan, so the loop is O(n²). Convert to a set first (O(1) average lookup) or use a formula.
  3. Why prefer XOR over the sum in C or Java? The sum of a large n can overflow a fixed-size integer; XOR never produces more bits than its inputs. Python integers don't overflow.
  4. What's the difference between / and //? / is true division and always returns a float; // is floor division (rounds down) and returns an int for ints.
  5. How do you count frequencies without KeyError? counts[x] = counts.get(x, 0) + 1, collections.defaultdict(int), or Counter(nums). O(n) time, O(k) space.
  6. What is Counter.most_common(k)? The k most frequent (value, count) pairs, highest first; ties stay in first-seen order.
  7. Explain Boyer-Moore voting. Keep a candidate and a count; +1 for the same value, −1 for a different one, take a new candidate at 0. A majority (> n/2) survives the cancelling. O(n) time, O(1) space; verify with a second pass unless a majority is guaranteed.

Glossary

Term Meaning Example
Off-by-one error A loop or index that goes one step too far or stops one step too early range(1, len(nums)) misses the last number
range(a, b) The integers from a up to, but not including, b list(range(1, 4)) → [1, 2, 3]
in on a list A linear scan from the start: O(n) 3 in [1, 2, 3]
O(n) Time grows in step with the input size sum(nums)
O(n²) Time grows with the square of the input: 10× the data, 100× the time i not in nums inside a loop
O(n log n) Sorting-level growth sorted(nums)
O(1) space Extra memory that doesn't grow with the input a few variables
O(k) space Extra memory that grows with k, the number of different values a dict of counts
Gauss's sum formula 1 + 2 + … + n = n(n + 1) / 2 n = 5 → 15
True division / Division that always returns a float 6 / 2 → 3.0
Floor division // Division rounded down; int for ints 7 // 2 → 3, -7 // 2 → -4
float A number with a decimal point 3.0
Bitwise operator Works on the individual bits (0s and 1s) of numbers ^, &, \|
XOR ^ Bitwise exclusive or: 1 where the bits differ 3 ^ 5 → 6, 5 ^ 5 → 0
Overflow A result too big for a fixed-size integer type (C, Java), giving a wrong value sum of 1..n for huge n in C
perf_counter() time.perf_counter(), a high-resolution stopwatch timing the slow version
KeyError Raised when reading a dict key that doesn't exist {}["Asha"]
dict.get(key, default) The value, or the default if the key is missing counts.get("Asha", 0)
Dictionary comprehension Builds a dict in one expression {x: x * x for x in nums}
list.count(x) How many times x appears; scans the whole list, O(n) [1, 2, 1].count(1) → 2
collections.Counter A dict subclass that counts items in one pass Counter("banana")
most_common(k) The k most frequent (item, count) pairs, highest first c.most_common(2)
Counter.update() Adds counts from an iterable c.update(["Neha"])
Tie order Equal counts in most_common stay in first-seen order Asha before Neha
Majority element A value appearing more than n // 2 times 2 in [2, 2, 1, 1, 2, 2, 3]
Boyer-Moore voting One-pass majority algorithm that cancels pairs of different votes candidate + count
Candidate The value the voting pass ends with; only possibly the majority 3 for [1, 2, 3]
Verify pass A second pass that checks the candidate really has more than half nums.count(candidate) > len(nums) // 2
Conditional expression a if condition else b in one line 1 if x == candidate else -1
set Unordered collection without duplicates, O(1) average lookup seen = set()

Summary

  • Missing number from 1 to n: n = len(nums) + 1. Test the last number to catch the off-by-one. Avoid in on a list inside a loop (O(n²)). Use n * (n + 1) // 2 - sum(nums) (//, not /) or XOR, both O(n) time, O(1) space.
  • Frequency: counts[x] += 1 on a new key raises KeyError; use counts.get(x, 0) + 1 or Counter. Never list.count() inside a loop. Counter gives 0 for missing keys, most_common(), and update(). O(n) time, O(k) space.
  • Majority: sorting and taking the middle assumes a majority exists. Boyer-Moore voting finds a candidate in O(n) time, O(1) space; a verify pass turns it into a correct answer, or None.

Next episode: List questions IV: two-sum, moving zeros to the end, and the trap of changing a list while you loop over it.