Hashable Keys & Prefix Passes

Arrays & Hashing, lesson 3 of 3

Hashable Keys & Prefix Passes

Encode state as a tuple key, and answer "everything except i" with prefix and suffix passes.

12 min, 0 of 3 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

The harder hashing problems are mostly about choosing the key. Ask: "what exactly makes two things the same?" and encode only that as a tuple.

  • Anagrams: the letter counts, as a 26-tuple
  • Sudoku: (row, digit), (col, digit) and (box, digit) where the box is (r // 3, c // 3)
  • Points on a line: the slope, as a reduced fraction (dy, dx)
Example

Two ways to build an anagram key

Both work. The count tuple is O(k) per word, which matters for long words; the sorted string is shorter to write. The tuple(...) call is essential: a list can't be a key.

Example

Which 3x3 box is a cell in?

Integer division squashes rows 0-2 to 0, 3-5 to 1, 6-8 to 2, so (r // 3, c // 3) names the box. This "coarsen the coordinates" trick shows up in grid problems everywhere.

Quiz

What does this print?

Prefix and suffix passes. Some array problems want, for every index i, an answer built from everything except nums[i]. Recomputing it per index is O(n²). Instead, precompute:

  • left[i]: the combination of everything before i
  • right[i]: the combination of everything after i

Then the answer is left[i] combined with right[i]. For products:

nums   = [ 2,  3,  4,  5]
left   = [ 1,  2,  6, 24]  (before i)
right  = [60, 20,  5,  1]  (after i)
answer = [60, 40, 30, 24]  left * right
Example

Left and right passes, traced

Two linear passes, no division, and zeros are handled for free. You can even drop the right list and keep a running product in one variable. Swap * for max or + and the same shape solves other "everything but i" questions.

A set as a "start of run" detector. To find the longest run of consecutive values (like 1, 2, 3, 4) without sorting, put everything in a set. A value x starts a run only if x - 1 is missing. Only from starts do you count upward, so every value is visited a constant number of times: O(n) total.

Example

Runs from their starts

Without the x - 1 check, every value would walk its own run and a list like range(n) would take O(n²).

Quiz

What does this print?

Exercise

Max of everyone else

Write max_except_self(nums) that returns a list where position i holds the largest value among all elements except nums[i]. nums has at least 2 elements.

max_except_self([3, 1, 4, 1, 5]) is [5, 5, 5, 5, 4].

Use a left pass and a right pass: O(n), not O(n²).