Python dicts, sets and sorted keys

Why it matters

Many slow programs share one habit: they search a list again and again to answer "have I seen this before?" or "what is the value for this name?" Each search walks through the list, so the total work grows with the square of the input. A dict or a set answers the same question in about one step, and that change turns many O(n squared) solutions into O(n). You will use these two types in almost every Python program you write after this course.

This lesson covers three ideas. A dict finds a value by its key very quickly, but it is built for lookups, not for asking questions about order. A set is a dict with only keys, used to store unique items. Python has no built-in sorted map, so the last section shows how to keep keys in order with the bisect module and when a sorted structure is the better choice. Each one has a cost, and choosing well is the skill this lesson builds.

Start from the problem: searching a list is slow

Suppose you have a list of a thousand student names and you want to know whether "Meera" is in it. With a list, you check each name in turn. On average you look at half the list, so about 500 comparisons. Ask the same question for every student in a list of a thousand, and you make about half a million comparisons.

A phone book shows a better way. You do not read the whole book to find a name. You jump to the right page almost at once, because the book is arranged by name. A dict gets a similar result without needing a sorted list. It works out where a key should live from the key itself, then looks only there.

Words you need first

A mapping stores key-value pairs. The key is the name you look up by, and the value is the data attached to it. In Python, the mapping type is dict. In a phone book, the key is the name and the value is the number. A dict allows each key to appear only once. If you store a second value under the same key, the new value replaces the old one.

A set stores items with no duplicates. It answers one question very quickly: "is this item in the set?"

A hash is a whole number that Python computes from a key. Strings, numbers, tuples of simple values and frozen dataclasses (classes whose fields cannot be changed) all have one. The built-in function hash(x) shows it. Two keys that are equal must produce the same hash. The rule is written in the rules for __eq__ and __hash__, which a later section explains.

A slot is one place in the table that stores a dict's entries. A collision happens when two different keys want the same slot. CPython, the standard Python interpreter, handles a collision by checking another slot in a fixed order until it finds a free one or the matching key. Collisions are normal. A good dict keeps them rare.

Finally, a sorted structure keeps its items in order by key. Python's dict does not do this. It remembers the order in which keys were added, which is a different thing. The bisect section below covers sorted keys.

Creating dicts and sets

A dict is written with curly brackets and a colon between each key and value. A set is written with curly brackets and no colons. An empty set cannot be written with brackets, so it uses set():

count = {}
seen = set()
prices = {100: "tea", 250: "coffee"}

The keys of a dict and the items of a set must be hashable, which means they have a hash that never changes. Numbers, strings and tuples are hashable. Lists and dicts are not, and the common mistakes section shows the error.

A worked example: counting words

Counting how often each item appears is the most common use of a dict. The pattern is always the same. For each item, read the current count, add one, and store it back. The method get reads the count, or returns a default value when the key is missing.

The output is:

to: 2
missing: None
has xyz? False
distinct: 4
sorted: {'be': 2, 'not': 1, 'or': 1, 'to': 2}
be -> 2
not -> 1
or -> 1
to -> 2

Trace the loop for the first five words. The word to is not yet a key, so get returns 0. The program stores 1 under to. The word be is new, so it gets 1. The word or is also new, and it gets 1. The next word, not, gets 1. The word to comes back, and this time get returns the stored 1, so the program stores 2. At the end, to holds 2, be holds 2, or holds 1 and not holds 1. That is why len(count) reports 4 distinct words, even though the list has six entries.

Notice count.get("xyz"). It returns None, not an error, because a missing key is an ordinary answer. The in test is the clear way to ask whether a key exists. Compare that with count["xyz"], which raises KeyError: 'xyz' when the key is missing. Use [] when a missing key is a bug, and get when it is a normal case.

Also notice the sorted printing. A dict's printing order is the order its keys were added, not alphabetical order. The program sorts the items to print the words alphabetically. Sort whenever you need a fixed order for output.

How a dict finds a key

When you read or store a key, the dict does three things. It computes the key's hash. It turns the hash into a slot number, using the hash modulo the size of the table. It then looks in that slot for the key, comparing with == to find the exact match. If the slot holds a different key, it checks the next slot in its probing order until it finds the key or an empty slot.

With a good hash function and a table that is not too full, the search checks only one or two slots. That is why the average cost is O(1). A lookup for a key that is missing checks slots until it reaches an empty one, which is also about one or two checks.

CPython grows the table when it gets about two-thirds full. The growth is the same trade as the growing list in the first lesson of this module: a rare, expensive step that makes the normal steps cheap on average. The exact growth steps depend on the Python version, so you do not need to memorise them.

The hash of a string is randomised each time Python starts, unless you set the environment variable PYTHONHASHSEED. That is why the order of a set of strings can change between runs. Never rely on the order of a set of strings. Sort them first if the order matters.

Iterating and removing

A dict gives you three views: the keys, the values and the items. Use keys() when you need only the keys, values() when you need only the values, and items() when you need both. Each item is a pair of key and value, and a for loop can unpack it into two names.

Changing the dict while you loop over one of these views is an error. Python raises RuntimeError with the message dictionary changed size during iteration, as the common mistakes section shows. Remove items after the loop, or loop over a copy of the keys with list(d).

Counting and grouping helpers

Two helpers in the standard library handle the most common dict patterns in one line each.

The class Counter from collections counts items. Counter(words) builds the same counts as the loop in the first example.

The class defaultdict from collections creates a missing value the first time you touch a key. defaultdict(list) makes an empty list for each new key, so you can append without checking first.

The output is:

Counter({'to': 2, 'be': 2, 'or': 1, 'not': 1})
{'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']} 3

The second example groups words that are anagrams of each other. An anagram is a word made from the same letters in another order, such as eat and tea. The key for each group is the word with its letters sorted, so every anagram of eat shares the key aet. The line "".join(sorted(w)) sorts the letters and joins them back into one string.

The keys appear in the order their first word arrived: aet from eat, then ant from tan, then abt from bat. Python dicts keep insertion order, so that order is kept. The defaultdict removes a common source of bugs. Without it, you would check whether the key exists, create a list if not, and then add the word. A defaultdict does all three steps in one line.

set: unique items

A set is a dict that stores only keys. It has no values, because the item is the whole key. Adding an item that is already present does nothing. The add method returns None in both cases, so to check for a repeat you test membership before the add. The in test checks membership in O(1) on average.

The program below uses sets to answer membership questions and to find overlaps between two groups. Sets print in no fixed order, so the program sorts before it prints.

The output is:

3 already in a: True
9 now in a: True
common: [4, 5]
union: [1, 2, 3, 4, 5, 6, 9]
only a: [1, 2, 3, 9]
unique count: 3

The operator & gives the intersection, the items in both sets. The operator | gives the union, all items from either set. The operator - gives the difference, the items in the first set but not in the second. The last part is the everyday use of a set. Adding every value of a list to a set removes duplicates. The length of the set is the count of distinct values. This pattern is faster than comparing each pair of values, and it is simple enough to write in a few lines.

Sorted keys: when order is the question

A dict cannot answer questions such as "what is the largest key below 300?" Those questions need the keys in sorted order. Python's standard library has no sorted map, so you build one from two parts: a sorted list of keys, and a dict for the values. The bisect module searches a sorted list with binary search, which you met in the first lesson of this module. Each search costs O(log n).

The two questions you will ask most are these. floor(x) gives the largest key less than or equal to x. ceiling(x) gives the smallest key greater than or equal to x. The function bisect.bisect_right finds the position just after the last key that is less than or equal to x, so the key before that position is the floor. The function bisect.bisect_left finds the position of the first key that is greater than or equal to x, so the key at that position is the ceiling.

The program below plays the role of a price list. The keys are prices in cents, and the values are product names. For each query it prints the nearest price below and the nearest price above. Save it as a file. When it asks for input, type this, one line at a time:

4
50
250
300
500

import bisect
 
 
class SortedPrices:
    def __init__(self):
        self.keys = []
        self.values = {}
 
    def put(self, key, value):
        if key not in self.values:
            bisect.insort(self.keys, key)
        self.values[key] = value
 
    def floor(self, x):
        i = bisect.bisect_right(self.keys, x) - 1
        return self.keys[i] if i >= 0 else None
 
    def ceiling(self, x):
        i = bisect.bisect_left(self.keys, x)
        return self.keys[i] if i < len(self.keys) else None
 
 
prices = SortedPrices()
prices.put(100, "tea")
prices.put(250, "coffee")
prices.put(400, "juice")
 
n = int(input())
for _ in range(n):
    x = int(input())
    below = prices.floor(x)
    above = prices.ceiling(x)
    b = "none" if below is None else f"{below} {prices.values[below]}"
    a = "none" if above is None else f"{above} {prices.values[above]}"
    print(f"{x}: below {b}, above {a}")
print("first", prices.keys[0], "last", prices.keys[-1])

The output is:

50: below none, above 100 tea
250: below 250 coffee, above 250 coffee
300: below 250 coffee, above 400 juice
500: below 400 juice, above none
first 100 last 400

Check the query 250. It is an exact match, so floor and ceiling both return 250. The query 50 is below every key, so there is no floor, and the program prints none. The query 500 is above every key, so there is no ceiling. These missing answers are normal, and the None check handles them. Forgetting that check is a common bug, and the common mistakes section shows what it looks like.

A dict cannot answer these questions in any efficient way. To find the nearest price below 300 with a dict, you would have to check every key. The sorted list answers in O(log n) for the search, and insort inserts a new key in O(n), because later keys move one place. Use sorted keys when the order is part of the question. Use a plain dict when only lookups matter. For a sorted map that also inserts quickly, the third-party package sortedcontainers is the common choice, but it is not in the standard library.

Insertion order

A plain dict in Python keeps the order in which keys were first added. That is a guarantee of the language, so you can rely on it. A dict that you build from input, then print, shows the keys in input order. The anagram groups above printed in that order for this reason.

The insertion order is not the same as sorted order. A dict with keys added as c, a, b prints in that order, not in alphabetical order. Sort the items when you need alphabetical output.

Two-sum: the classic O(n) pattern

The two-sum problem asks: given a list and a target number, find two positions whose values add up to the target. The brute-force solution checks every pair, which is O(n squared). The dict solution makes one pass.

For each number, the program asks: "have I already seen the number I need to reach the target?" The needed number is the target minus the current value. If it is in the dict, you have found the pair. If not, you store the current value with its position and move on. The dict stores each value with its index, so you can return both positions.

Save the program as a file. When it asks for input, type this, one line at a time:

4
2 7 11 15
9

n = int(input())
a = list(map(int, input().split()))
target = int(input())
 
seen = {}
found = False
for i in range(n):
    need = target - a[i]
    if need in seen:
        print(seen[need], i)
        found = True
        break
    seen[a[i]] = i
 
if not found:
    print("no pair")

The output is:

0 1

Trace it. At index 0 the value is 2, so the needed number is 7. The dict is empty, so 7 is not there. The program stores 2 with index 0. At index 1 the value is 7, so the needed number is 2. The dict holds 2 at index 0, so the program prints 0 1 and stops.

Notice the order of the two steps inside the loop. The program checks for the partner first and stores the current value second. If it stored first, a number could pair with itself: for target 8 and value 4, the number 4 would find itself. Storing after checking keeps each pair to two different positions.

The cost is O(n) time and O(n) space, because the dict can hold up to n values. The nested-loop version uses no extra space but costs O(n squared) time. In an interview, state both options and say which one you would ship, and why.

Prefix sums with a dict

The two-sum pattern generalises to a harder problem: how many contiguous parts of a list add up to exactly k? A prefix sum is the total of all values up to a point. If the prefix sum at position j is P[j] and at an earlier position i is P[i], then the part between them adds up to P[j] - P[i]. You need that difference to equal k, so you need P[i] = P[j] - k. A dict that counts how often each prefix sum has appeared answers that in O(1).

The program below reads n, the list and k, and prints the count. It stores the prefix sum 0 with count 1 before the loop starts, which covers parts that begin at the first value. Save it as a file. When it asks for input, type this, one line at a time:

5
1 2 3 -1 2
3

n = int(input())
a = list(map(int, input().split()))
k = int(input())
 
prefix_count = {0: 1}
prefix = 0
answer = 0
for v in a:
    prefix += v
    answer += prefix_count.get(prefix - k, 0)
    prefix_count[prefix] = prefix_count.get(prefix, 0) + 1
 
print(answer)

The output is:

2

The prefix sums are 1, 3, 6, 5, 7, and the starting 0 is in the dict. The parts that add up to 3 are 1 2 and 3 alone. The program finds them when the prefix is 3 and an earlier prefix is 0 (the part 1 2), and when the prefix is 6 and an earlier prefix is 3 (the part 3). The counting happens in the line that asks for prefix - k before the current prefix is stored, which is the same ordering rule as two-sum.

This pattern appears often in interviews, under names such as "subarray sum equals k" or "count of zero-sum ranges." It is one of the best examples of a dict turning a double loop into a single pass.

The equality and hash contract

Every key in a dict or a set must follow a contract. If two objects are equal according to ==, they must have the same hash. Strings, numbers, tuples of simple values and dataclasses with frozen=True follow it already. A class you write follows it only when you define both __eq__ and __hash__, and when the fields that decide equality cannot change.

Here is what breaks when a key object changes after it is stored. The program below stores a point as a key, then changes one of its fields.

The output is:

before change: home
after change, same key object: None
size still: 1
lookup by old value: None

The first lookup works, because the point has not changed. After the change, the point's hash is different, so the dict looks in the wrong slot and cannot find the key. The dict still holds one entry, which is why len is 1, but the entry cannot be reached by either lookup. The lesson is simple: do not change the fields of a key after you use it. Make key classes immutable. A frozen dataclass does this for you. Its fields cannot be assigned after creation, and Python gives it a hash automatically.

The output is:

start Cell(row=1, col=2)
caught: FrozenInstanceError cannot assign to field 'row'

A frozen dataclass makes a good key for a grid. Two cells with the same row and column are equal, and they hash the same, so grid[Cell(0, 0)] finds the value stored under another Cell(0, 0) object.

Keys that are tuples

A tuple is an easy key when you need several values together. grid[(row, col)] works without a class, because a tuple of numbers is hashable. The only rule is that the parts of the tuple must also be hashable. A tuple that holds a list is not hashable, and Python refuses it as a key.

How the table grows

A dict starts small and grows as you add entries. When it gets about two-thirds full, CPython creates a bigger table and moves every entry to its new slot, because the slot depends on the table size. One resize copies every entry, which is expensive. Between resizes, each lookup is cheap, and the table is never more than about two-thirds full. So the average cost of storing a key stays O(1) over a long run of stores.

You do not need to set a size for a dict, unlike a list with a preset length. Python handles the growth itself. Building a dict from a long list with dict(...) or a dict comprehension is already efficient.

An inverted index

A common use of a dict is to invert data. Suppose you have a dict from word to count, and you want all the words that share a count. Build a second dict from count to a list of words. For each item of the first dict, get its count and add the word to the list stored under that count. If you process the items in insertion order, the count 2 maps to the list of words to and be, and the count 1 maps to or and not. This is the same pattern as the anagram groups, with a different key. Whenever you need all items that share a property, think of a dict from that property to a list.

A pipeline: read, count, sort and print

Real programs chain several steps, and each step uses the collection that suits it. A word frequency report reads text, counts with a Counter, sorts the counts, and prints the top few.

The output is:

be 2
to 2

Trace it. The reading step splits the text into six words. The counting step gives be 2, to 2, or 1 and not 1. The sorting step sorts the items by count, largest first, with ties broken alphabetically. The key function (-item[1], item[0]) sorts by the negative count, so the larger count comes first, and then by the word. The printing step takes the first two entries.

The sort and the top-k step do the same job as the heap pattern from the third lesson. The heapq.nlargest function does the top-k work in O(n log k), while the sort costs O(n log n). For a small vocabulary the difference is invisible, which is why most programmers sort first and optimise only when a measurement asks for it.

The cost of the parts

The table below lists the cost of the operations you will use most. Each cost is on average, for a dict or a set with n items.

Look at the row for floor and ceiling. A dict does not answer it at all, because it has no order to search. This is the reason to pay the extra cost of a sorted list when the question needs order.

Choosing keys

The key type affects both correctness and speed. Strings and numbers are the most common keys, and they work well because they are immutable and their equality and hashing are already correct. A tuple is the next best choice for a key made of several parts. A frozen dataclass is the choice when the parts have names. A list works as a key only if you convert it to a tuple first. Python refuses lists as keys, so you cannot make the mistake of changing a list key after storing it.

Speed depends on the cost of the hash. Hashing a long string reads every character the first time, so a key of a thousand characters costs far more to hash than a number. When the key is a combination of two small numbers, use a tuple, so the lookup does one hash of two numbers.

Common mistakes

Assuming a dict is sorted. A dict keeps insertion order, not sorted order. Use sorted(d.items()) for sorted output, and the bisect approach for sorted lookups.

Reading a missing key with []. The line count["zzz"] raises KeyError: 'zzz'. Use count.get("zzz", 0) when a missing key is normal.

Using a list as a key. Python refuses it with this message:

TypeError: cannot use 'list' as a dict key (unhashable type: 'list')

Read the message from the start. The problem is that the key type is a list, which has no hash. Convert it to a tuple with tuple(items) and use the tuple.

Making a class unhashable by accident. If a class defines __eq__ and does not define __hash__, Python sets its hash to None. Using an instance as a dict key then raises TypeError: cannot use 'Bad' as a dict key (unhashable type: 'Bad'). Define __hash__, or make the class a frozen dataclass.

Changing a dict while looping over it. Adding or removing keys during a for loop over the dict raises RuntimeError: dictionary changed size during iteration. Loop over list(d) when you need to change the dict.

Checking key in d and then reading d[key] in two steps. This works, but it looks up the key twice. Prefer get, setdefault or a defaultdict, which do the work in one step.

Changing a key after storing it. The entry becomes unreachable, as the point example showed. Make keys immutable.

Putting None in a sorted structure. A sorted list must compare keys, and comparing None with a number raises TypeError: '<' not supported between instances of 'NoneType' and 'int'. A dict accepts None as a key, but a sorted list does not.

Using == for things that are the same object. Use is only for checks such as x is None. Use == to compare values, such as dict keys.

A debugging walkthrough: a count that is one too small

A program is meant to count how many times each letter appears in a word, but for the word aab it prints a: 0, and it should print a: 2. Here is the loop:

counts = {}
for c in "aab":
    counts[c] = counts.get(c, 0)
print(counts)

Trace it by hand. The first a is not in the dict, so get returns 0, and the program stores 0. The second a finds 0 stored, and it stores 0 again. The count never goes up, because the loop never adds one. The bug is that the code reads the count but forgets to add one before storing it. The printed output confirms it:

{'a': 0, 'b': 0}

The fix is counts[c] = counts.get(c, 0) + 1, or counts.setdefault(c, 0) followed by counts[c] += 1. A Counter does this in one line: Counter("aab").

The method of finding this bug is worth remembering. Pick a small input, write the dict after each step on paper, and compare each stored value with what you expected. A two-line trace usually shows the missing piece.

Variations and edge cases

An empty dict returns None from get and 0 from len. Loops over an empty dict simply do nothing, which is safe. Check the result of get before you use it, because None is the usual signal of a missing key.

A dict with one key works like any other. The interesting cases are missing keys and repeated keys. Test both.

Duplicate keys replace the value. The first value is gone. If you need to keep all values for a key, store a list as the value, as the anagram example did.

Negative numbers and zero are ordinary keys. The prefix-sum example needs the initial 0 entry for this reason, because a part that begins at the first value has prefix sum 0.

Very long strings as keys are fine, but each lookup computes the hash over the whole string. Keep keys small when you can.

Interview-style and real-world uses

When an interviewer asks for a solution faster than O(n squared), first ask whether a dict or a set can remove the inner loop. Two-sum, duplicate detection, grouping and counting usually can. Explain your choice in one sentence: "I store each value as I go, so each lookup for the partner is O(1), and the whole pass is O(n)."

When an interviewer asks for sorted results or the nearest neighbour, think of sorted keys with bisect, not a plain dict. The cost is O(log n) per search, and the answer comes out in order. Explain that trade in the same breath as the choice.

In real software, dicts are everywhere. A web framework looks up a route by its path. A cache stores results by their input. A compiler records each variable name and its type. A database index is a sorted structure on disk. Almost every program you will write after this course stores something by a key, which makes dicts and sets some of the most useful tools in Python.

Practice

1. Count how often each character appears in "mississippi" with a dict. Print the counts sorted by character.
2. Check whether a list has duplicates using a set. Explain why len(set(a)) != len(a) is a signal, and what the loop version does differently.
3. Why does a sorted structure not allow a None key but a dict does? Hint: think about what a sorted structure must do with each key when it places it.
4. Write a function that returns the first character of a string that appears only once, using a dict for the counts. Keep the order of first appearance. Return a space when there is none.
5. Given a list of numbers, find the length of the longest run of consecutive values, such as [100, 4, 200, 1, 3, 2], whose longest run is 1 2 3 4. Use a set and avoid sorting.
6. Given a sorted list of event times and a dict from time to name, write a function that returns the name of the event closest in time to a given time. Use bisect.
7. Write a function that counts pairs of equal numbers in a list using a dict of counts. Explain why the answer for four equal values is 6.
8. Explain why storing the current value before looking for its partner in two-sum can give a wrong answer for the target 8 and the list [4].
9. A coworker stores a list as a key in a dict, then adds an item to it. Python refuses the key. Explain why, and show the fix. Then explain what would happen with a custom class whose hash depends on a list field that changes after it is stored.
10. Write a program that reads words one per line until the word end, and prints each word with the number of times it appeared, in order of first appearance.

Exercise 1. Show the answer:

counts = {}
for ch in "mississippi":
    counts[ch] = counts.get(ch, 0) + 1
print(dict(sorted(counts.items())))

The output is {'i': 4, 'm': 1, 'p': 2, 's': 4}.

Exercise 2. Show the answer:

def has_duplicate(a):
    seen = set()
    for v in a:
        if v in seen:
            return True
        seen.add(v)
    return False

The check v in seen comes before the add, so a repeat is found the moment it appears. The one-line version len(set(a)) != len(a) answers the same question, but it always builds the full set. The loop stops early.

Exercise 3. Show the answer: a sorted structure must compare each new key with the keys it already has, to decide where the new key goes. Comparing None with a number has no meaning, so the comparison raises TypeError. A dict never compares keys for placement. It uses only the hash and the equality test, and None has a hash like any other value, so the dict accepts it.

Exercise 4. Show the answer:

def first_unique(s):
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    for ch, n in counts.items():
        if n == 1:
            return ch
    return " "

The dict keeps the characters in first-seen order, so the first entry with count 1 is the first unique character. For "swiss" the answer is w.

Exercise 5. Show the answer:

def longest_run(a):
    seen = set(a)
    best = 0
    for v in seen:
        if v - 1 not in seen:
            length = 1
            while v + length in seen:
                length += 1
            best = max(best, length)
    return best

Only the start of a run, where v - 1 is absent, extends a run, so each value is walked at most once. For the example list the answer is 4.

Exercise 6. Show the answer:

import bisect
 
def nearest(times, t):
    keys = sorted(times)
    i = bisect.bisect_left(keys, t)
    below = keys[i - 1] if i > 0 else None
    above = keys[i] if i < len(keys) else None
    if below is None:
        return times[above]
    if above is None:
        return times[below]
    return times[below] if t - below <= above - t else times[above]

For {9: "standup", 13: "lunch", 17: "review"} and time 14, the answer is lunch, because 13 is 1 away and 17 is 3 away.

Exercise 7. Show the answer: count each value, then for each count c add c * (c - 1) // 2. Four equal values make 4 * 3 // 2 = 6 pairs. The Counter class from collections gives the counts in one line.

Exercise 8. Show the answer: for [4] and target 8, the value 4 is stored first, and then the program looks for 4, which is its own partner. It finds the value and returns 0 0, which uses one position twice. Checking first and storing second avoids this.

Exercise 9. Show the answer: Python refuses a list as a key, with unhashable type: 'list', because a list can change and so it has no fixed hash. The fix is tuple(items), which cannot change. A custom class whose hash depends on a list field has the same problem in a different form. The hash changes when the list changes, so the dict looks in the wrong slot and the entry becomes unreachable. The fix is to build the hash from fields that never change, or to store a tuple.

Exercise 10. Show the answer:

seen = {}
while True:
    w = input()
    if w == "end":
        break
    seen[w] = seen.get(w, 0) + 1
 
for word, n in seen.items():
    print(word, n)

What you now know

• A dict finds a key in O(1) on average by hashing it. It keeps insertion order, not sorted order.
• A set stores unique items with O(1) average in and add.
• Use get, Counter and defaultdict to update counts and groups in one step.
• Python has no built-in sorted map. A sorted list of keys with bisect answers floor and ceiling questions in O(log n).
• Keys must be hashable. Make key classes immutable, and never change a key after you store it.
• The two-sum and prefix-sum patterns use a dict to remove an inner loop and reach O(n).