pattern heroPT–23LeetCode Extension

Hash map

Keep everything you have seen in a hash table: it answers "have I seen this?" at once, without looking through the data again. So one pass is enough instead of comparing every item with every other.

Variant
P01 Hash mapFind a pair · 1×

Example problem: find the indices of two numbers in [2, 11, 6, 15, 3, 8] that add up to 19.

02111263154358seennumber: index—
not reached yetin the mapcurrent numberits partnerthe answer

Start with an empty map

seen = {}i = –need = –
01/25
restart · back · play · step
Speed
1function twoSum(nums, target):
2 seen = empty map
3 for i from 0 to len(nums) - 1:
4 need = target - nums[i]
5 if need in seen:
6 return [seen[need], i]
7 seen[nums[i]] = i

← → step · space play/pause

How to recognise

a pair with a given sum or difference, duplicates, counting values, or any "have I seen this before?" question.

How to solve problems like this

  1. Decide what you will need to find later: a partner, a repeat, a count.
  2. Pick the key you will search by and what to store with it: an index, a count.
  3. Walk the input once. For each item, first look up what it needs.
  4. Then store the item, so the items after it can find it.

Variant: Counting

The same, but store how many times an item appeared, not where. Use it when it matters how many of each there are, not where they stand, as with anagrams.

  1. Count what you have: a map from each item to how many times it appears. For lowercase letters an array of 26 works too.
  2. Walk what you need and take one away each time. A count below 0 means something is missing, and you may stop right there.
  3. Two words are anagrams when they have the same length and every count ends at 0. To group anagrams, give each word a key all its anagrams share, such as its sorted letters, and collect the words in a map under that key.
  4. The majority element is the same idea: count every value and return the one whose count goes over n / 2.

Where it's used

  • Python. A Python dict is a hash table. Python looks up module variables and object attributes in dicts too, so a hash table is at work in almost every line of a program.
  • Redis. Redis keeps all its keys in a hash table, so reading a value by its key is instant however many keys there are.
  • Databases. To join two tables, PostgreSQL can put the smaller one into a hash table by key, then walk the bigger one and find each row's partner at once. This is called a hash join.