Looking up a value instead of a position
A list finds its elements by position: nums[3] is the element at index 3. Many questions are about the values instead: whether a name has appeared before, how many times a word appeared, or which price goes with a fruit. A list can answer them only by searching, comparing the wanted value with each element in turn until one matches or the list runs out.
Here is a question of that kind. A website writes the name of each visitor to a log, one name per line, and you want to know how many different people visited. If the log reads ana, bo, ana, cy, the answer is 3: ana visited twice, but she is one person.
Counting different values with a list
The direct approach keeps a list, seen, of the names met so far. For each name it searches seen, and appends the name only when the search finds nothing. The first line of the input holds the number of names.
n = int(input())
seen = []
for i in range(n):
name = input()
if name not in seen:
seen.append(name)
print(len(seen))Python details
Python carries out name not in seen by comparing name with each element of seen in turn, from the first.
On a log of a few hundred names this finishes at once: 300 names need at most comparisons, which a computer does in a moment.
The cost of searching a long list
A list search slows down as the list grows. Suppose the log has names, a size judge problems often allow, and almost all of them are different. Then seen keeps growing, and the search for the -th name compares it with all names stored before it. Over names the comparisons add up to
Python manages about simple steps a second, so that is seconds, where a judge usually allows 2.
A list keeps no record of where a value might be, so a search for a value that is not there has to check every element. A long log needs a container that answers "is this value here?" without looking at everything it holds.
Sets: has this value appeared?
Both languages provide such a container, the set. Adding a value that is already there changes nothing, so the size of a set is the number of different values added to it.
Definition
A set is a collection of values without repeats. It can add a value, remove one, and tell whether a value is in it, without searching through every value it holds.
The set operations
This program adds three words to a set, one of them twice, then checks for two words and removes one.
kinds = set()
kinds.add('apple')
kinds.add('orange')
kinds.add('apple')
print(len(kinds))
print('apple' in kinds)
print('pear' in kinds)
kinds.remove('apple')
print(len(kinds))Python details
{} makes an empty dictionary, the structure the next part introduces, so an empty set is written set(). A set can also be written out with braces, as in {1, 2}.
remove stops with KeyError when the value is not in the set. discard removes a value if it is there and does nothing otherwise.
The second apple changed nothing, so the size is 2. With these operations the visitor count needs no search through the stored names: add every name to a set and print its size.
Counting different values with a set
n = int(input())
names = set()
for i in range(n):
names.add(input())
print(len(names))A Python set is a hash table: it turns each value into a number, its hash, and uses that number to go straight to the slot where the value would be stored. An add or a check takes a few steps on average, however many values the set holds. At about 5 steps a name, names take around steps in all, about a tenth of a second, where the list search needed comparisons. The Deeper read at the end of the lesson shows how the slots work.
len(set(names)) counts the different values of a list names in one expression, since set(...) builds a set from any sequence.
Four judge problems practise this. Gacha is the visitor count with prize names in place of visitors, so the program above solves it as it stands.
A lottery is drawn times, and each draw gives an item whose kind is a word . How many different kinds of item come out?
The first line holds , and each of the next lines holds one word.
Constraints
- Each has 1 to 10 lowercase letters
Sample 1 · Input
3 apple orange apple
Output
2
Sample 2 · Input
4 aaaa a aaa aa
Output
4
Kagami Mochi needs one observation first. Two cakes of the same diameter can't both go in one stack, while cakes of different diameters always can, once they are put in order, so the answer is the number of different diameters.
A kagami mochi is a stack of round rice cakes where each cake is strictly smaller across than the one below it. There are rice cakes with diameters , and any of them may be used. How many layers can the tallest kagami mochi have?
The first line holds , and each of the next lines holds one diameter.
Constraints
Sample 1 · Input
4 10 8 8 6
Output
3
Sample 2 · Input
3 15 15 15
Output
1
Write and Erase needs the removing operation, and Anton and Letters asks for the number of different letters in a line.
Dictionaries: a value for each key
A set answers yes or no. Counting needs more: how many times each word has appeared, so each word needs a number attached to it.
A dictionary stores pairs. The first part of each pair is a key, and the second is the value stored under it. Keys are unique, as the values of a set are, and a dictionary finds a key as quickly as a set finds a value. Python's dictionary is the dict. To count words, make each word a key and store its count as the value.
Definition
A dictionary maps keys to values. Each key appears once, and counts[key] reads or changes the value stored under it.
Dictionary literals and lookups
A dictionary can be written out in full: pairs between braces, each pair a key, a colon and a value. This one holds the prices of three fruits. The program looks one price up, adds one and changes one.
price = {'apple': 120, 'pear': 90, 'fig': 200}
print(price['pear'])
print(len(price))
price['kiwi'] = 60
price['pear'] = 95
print(price)
print(list(price))
print({'a': 1, 'a': 2})
board = {(0, 0): 'start', (2, 3): 'goal'}
print(board[(2, 3)])
print('pear' in price, 95 in price)
del price['fig']
print(list(price))Python details
list(price) gives the keys, in the order they were added.
price['pear'] looks up the key pear and gives 90. Assigning to a key that exists, as price['pear'] = 95 does, replaces its value. Assigning to a new key, kiwi, adds a pair, so the dictionary grows from 3 pairs to 4. Because each key appears once, a literal that repeats a key keeps only the last value: {'a': 1, 'a': 2} is {'a': 2}. 'pear' in price is True while 95 in price is False, because in looks only at the keys. del price['fig'] removes a key and its value; price.pop('fig') does the same and gives back the value.
Not every value can be a key. A key must be hashable: Python computes a fixed number, its hash, from it. Numbers, strings and tuples of hashable values qualify, such as the positions (2, 3) that board uses. A list does not, so {[0, 0]: 'start'} stops with a TypeError whose message includes unhashable type: 'list', and neither does a tuple holding a list, such as (1, [2, 3]). The Deeper read on hash tables explains why.
Step through a word count
This program counts words, then prints each word with its count. Watch the counts row in the frame: a new word adds a key, and a repeat raises a count. The demo has three inputs. The second starts with pear; note which word is printed first.
The if is needed because counts[w] += 1 on a missing key stops with KeyError. After import collections, collections.Counter(words) counts a whole list in one call, and a collections.defaultdict(int) starts every missing key at 0.
Counting the earlier copies of a word
A count is useful before the input ends, too. This problem needs, for each word, how many times it appeared earlier.
words are given in order. For each one, print it unchanged if no earlier word equals it. If earlier words equal it, print it followed by in parentheses.
The first line holds , and each of the next lines holds one word.
Constraints
- Each word has 1 to 10 lowercase letters
Sample · Input
5 newfile newfile newfolder newfile newfolder
Output
newfile newfile(1) newfolder newfile(2) newfolder(1)
In the sample, the first newfile has no earlier copy, so it prints as it is. The second has one earlier copy and becomes newfile(1), and the third has two and becomes newfile(2). So for each word the program reads the word's count so far, prints the word with that count, and only then adds one to it. The count must go up after printing, or the first newfile would come out as newfile(1).
n = int(input())
count = {}
for i in range(n):
s = input()
x = count.get(s, 0)
if x == 0:
print(s)
else:
print(s + '(' + str(x) + ')')
count[s] = x + 1Python details
count.get(s, 0) returns the value stored under s, or 0 when s is not a key, where count[s] would stop with KeyError.
Each word costs one lookup and one update, so even words take well under a second.
Dictionary methods
The programs so far read a dictionary one key at a time. A dictionary's methods, functions attached to it and called with a dot like count.get(s, 0) (or s.upper() on a string), can also hand over all its contents at once: keys() gives the keys, values() the stored values, and items() each key with its value.
When the pairs are already in a list, dict(...) turns them into a dictionary, and a dictionary comprehension, written like a list comprehension with braces and a colon, builds a new dictionary from an old one, such as every price doubled.
price = {'apple': 120, 'pear': 90, 'fig': 200}
print(list(price.values()))
print(sum(price.values()))
for name, cost in price.items():
print(name, cost)
print(price.get('kiwi', 0))
pairs = [('kiwi', 60), ('plum', 80)]
print(dict(pairs))
print({name: cost * 2 for name, cost in price.items() if cost < 150})Python details
for name, cost in price.items(): unpacks each pair into two names, the same unpacking as for a, b in throws.
The values add up to , and get gives 0 for kiwi, which is not a key. The comprehension keeps the fruits priced under 150 and doubles their prices: apple becomes 240 and pear 180, and fig, at 200, is left out.
The order in which keys come out
In the word-count demo, the input pear, apple, pear, fig printed pear first. A for loop over a dict visits the keys in insertion order, the order in which they were first added.
A set keeps no order at all. A set of small integers often prints sorted, as {3, 1, 2} prints {1, 2, 3}, but {10, 2, 33} prints {33, 10, 2}. For strings the order can change from one run to the next, because each time Python starts, it mixes a new random number into the hash of every string. The next problem asks for its output in sorted order.
There are votes, and each one has a word written on it. Print every word that is written on the largest number of votes, in alphabetical order, one per line.
The first line holds , and each of the next lines holds one vote.
Constraints
- Each word has 1 to 10 lowercase letters
Sample 1 · Input
7 beat vet beet bed vet bet beet
Output
beet vet
Sample 2 · Input
4 ushi tapu nichia kun
Output
kun nichia tapu ushi
In the first sample, beet and vet each appear on two votes and the other words on one, so the answer is beet and vet. In the second, every word appears once, so all four are printed, sorted.
The program makes two passes: count the votes in a dictionary, then find the largest count and print the words that have it. On the second sample, walking the dict would print ushi first, the order the votes came in, so it walks sorted(count) instead.
Printing the most common words in order
n = int(input())
count = {}
for i in range(n):
s = input()
count[s] = count.get(s, 0) + 1
best = max(count.values())
for s in sorted(count):
if count[s] == best:
print(s)Python details
count.get(s, 0) + 1 is the old count, or 0 for a new word, plus one. max(count.values()) picks the largest count, and sorted(count) gives the keys as a sorted list.
Sorting different words at the end takes a few million comparisons, well under a second.
Lookup cost and loop order by structure
| Structure | Order of a loop | Steps to find a value |
|---|---|---|
Python list, C++ vector (search) | Index order | Up to |
Python set, dict | Set: none; dict: insertion | A few, on average |
C++ set, map | Sorted | About , the halvings from to 1 |
C++ unordered_set, unordered_map | None | A few, on average |
Python has no sorted set or dictionary built in. When the keys are needed in order, sort them once at the end, as the voting program did.
Small integer keys
Sets and dictionaries accept almost any key: words, large numbers, negative numbers. Sometimes the keys are far more limited. Every Kagami Mochi diameter is between 1 and 100, so a list of 101 entries could record in seen[d] whether diameter d appeared, with index 0 unused. Reaching seen[d] takes one step, with no hashing and no tree, because the list goes straight to position d. A list works as a dictionary whenever the keys are integers from 0 up to a limit known in advance.
Letters can be turned into such keys. The lowercase letters have consecutive character codes, so ord(c) - ord('a') is 0 for a and 25 for z.
A string of lowercase letters is given. Print the alphabetically smallest lowercase letter that does not appear in , or None if every letter appears.
Constraints
- consists of lowercase English letters
Sample 1 · Input
atcoderregularcontest
Output
b
Sample 2 · Input
abcdefghijklmnopqrstuvwxyz
Output
None
In the first sample, a appears but b does not, so the answer is b. The program keeps a list of 26 true-or-false entries, one per letter, and marks each letter of . Then it walks the list from a and stops at the first unmarked letter.
A list indexed by letter
s = input()
seen = [False] * 26
for c in s:
seen[ord(c) - ord('a')] = True
answer = 'None'
for i in range(26):
if not seen[i]:
answer = chr(ord('a') + i)
break
print(answer)Python details
[False] * 26 makes a list of 26 False values, and chr turns a character code back into a letter.
The program marks each of the up to letters of and then checks at most 26 entries. A set would also work, but walking the list's indexes 0 to 25 in order finds the smallest missing letter directly.
Deeper read: how a hash table finds a value
A hash table keeps an array of slots. To store a value, it computes the value's hash and uses that number to pick a slot, for example by taking its remainder after dividing by the number of slots. To check for a value later, it computes the same hash and goes to the same place. When the table fills up, it moves to a larger array, so most slots stay free.
Two values can still be sent to the same slot. Python's set and dict keep one entry per slot, and when a slot is taken they try other slots in a fixed order until they find the value or a free slot.
Two consequences follow. First, a key must not change once it is stored, or its hash would point to the wrong slot. That is why a list cannot be a set element or a dictionary key, while a tuple such as (3, 4) can.
Second, "a few steps" is an average. If many keys clash, every lookup tries slot after slot. A small integer's hash is the integer itself (hash(5) is 5), so it is easy to choose many integers that clash, and on Codeforces some tests are built on purpose to slow down dictionaries and sets of integers.
Common mistakes
Checking whether a word was seen by reading its count, as in
count[s] > 0.- Where it breaks
- With the keys
appleandorange, Python stops oncount['kiwi'] > 0withKeyError: 'kiwi'. C++ runs, butcount["kiwi"]addskiwiwith the count 0, socount.size()becomes 3 instead of 2, and a later loop printskiwi 0. - The fix
- Ask with
s in countin Python orcount.count(s)in C++, which only look, and readcount[s]once you know the word is there.
In Python, deleting keys from a
dictinsidefor k in d:.- Where it breaks
- For
d = {'a': 1, 'b': 2}, deleting'a'inside the loop stops the program withRuntimeError: dictionary changed size during iteration. - The fix
- Loop over a copy of the keys,
for k in list(d):, or build the dictionary you want with a comprehension.
Recall The input has up to $10^5$ numbers, each between 1 and $10^9$. The task is to count how many times each number appears. Which structure fits, and why not a list indexed by the number?
A dictionary, with each number as a key and its count as the value. A list indexed by the number would need entries, one per possible value, even though at most of them are used.
Recall A C++ `map` and a Python `dict` both receive the keys `pear`, `apple`, `fig` in that order. In what order does a loop visit them in each?
The map visits apple, fig, pear, sorted. The dict visits pear, apple, fig, the order the keys were added.
Key terms
| Term | Meaning |
|---|---|
| set | A collection of values without repeats that can tell quickly whether a value is in it. |
| dictionary | A collection of key and value pairs, each key once: Python's dict, C++'s map. |
| key | What a dictionary looks a value up by, such as a word. |
| value | What a dictionary stores under a key, such as the word's count. |
| hash table | A set or dictionary that finds a value through a number computed from it: Python's set and dict, C++'s unordered_set and unordered_map. |
| hashable | Able to be a Python set element or dictionary key: numbers, strings and tuples of hashable values, but not lists. |
| insertion order | The order in which keys were first added, which a Python dict keeps. |
| method | A function attached to a value and called with a dot: price.get('kiwi', 0). |
| dictionary comprehension | An expression that builds a dictionary from a sequence: {w: len(w) for w in words}. |
