Arrays
Loading
Loading
Arrays
Counting occurrences to collapse a nested search into a single pass.
By the end of this chapter
A great many quadratic solutions exist because the algorithm keeps re-deriving something it already computed. Counting once removes the inner loop.
# Quadratic: counts each value by rescanningdef most_common_slow(nums): best, best_count = None, 0 for value in nums: count = sum(1 for other in nums if other == value) if count > best_count: best, best_count = value, count return best # Linear: count once, then read the countsdef most_common(nums): counts = {} for value in nums: counts[value] = counts.get(value, 0) + 1 return max(counts, key=counts.get)| Situation | Use |
|---|---|
| Keys are letters a–z | An array of 26 counters |
| Keys are small bounded integers | An array indexed by the value |
| Keys are arbitrary or sparse | A hash map |
| Keys are tuples or strings | A hash map |
Counting needs the whole input; ordering needs the original sequence. Trying to do both in one pass leads back to a nested loop. Two clean passes stay linear.
def first_unique(items): counts = {} for item in items: counts[item] = counts.get(item, 0) + 1 # Second pass follows the ORIGINAL order, not the map's. for index, item in enumerate(items): if counts[item] == 1: return index return -1Can you recognise the pattern?
A nested loop where the inner loop only checks existence, counts occurrences, or looks for a complement.
Sign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for:
Before moving on: try 3 practice problems.