Arrays and Hashing
7 / 170Arrays and HashingLesson 2 of 10About 35 min
When order does not matter, a count is the whole content of the input.
Building one takes three lines. The .get(key, 0) call is what saves you from checking whether the key exists yet.
def counts_of(items): counts = {} for item in items: counts[item] = counts.get(item, 0) + 1 return counts print(counts_of("banana"))print(counts_of(["red", "blue", "red"]))The second half of the technique is spending a count rather than building one. Here is the useful question it answers: can you build a message out of the letters available in a magazine, using each letter at most as many times as it appears?
def can_build(message, letters): available = {} for ch in letters: available[ch] = available.get(ch, 0) + 1 for ch in message: if available.get(ch, 0) == 0: return False available[ch] -= 1 # spend it, so it cannot be reused return True print(can_build("note", "toonet"))print(can_build("noon", "onet"))Once the count map is the object you are reasoning about, a lot of different-sounding questions become one line each. Are these two collections the same? Equality. Does one fit inside the other? Every count on the left is at most the matching count on the right. What is left over? Subtraction.
None of these need a new technique. They need you to notice that the count map is the real object, and that the question is asking something about the relationship between two of them.
from collections import Counter pantry = Counter("aabbc")recipe = Counter("aab") print(all(recipe[item] <= pantry[item] for item in recipe)) # enough of everything?print(pantry - recipe) # what is spareWrite these without importing Counter, since the point is the loop. frequencies returns a plain dict of counts. times_buildable asks how many complete copies of a word you could make from a pile of letters. most_frequent returns the value with the highest count, breaking ties toward whichever value reached that count first.
Tests
print(frequencies("banana"))print(times_buildable("ab", "aabb"), times_buildable("ab", "aab"), times_buildable("ab", "aaa"))print(most_frequent([1, 2, 2, 3, 3]))print(most_frequent([]))Output
Run tests to see output.
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.