Skip to main content

Hash & Set

Trade memory for lookups. A scan that would otherwise need a second loop to ask "does this value exist anywhere else?" gets its answer in O(1) by remembering what it has already walked past - a set when only membership matters, a map when the position or count matters too.

The shape is almost always the same: one pass, one question per element, and the structure is updated as you go so that every answer it gives is about elements you have genuinely already seen.

Membership​

Only one bit of information is needed per value - have I met it before? A set answers that and nothing else.

1231nums123seenalready seen!duplicate found
Otto stashes each new value into the seen set as he passes it. When the second 1 arrives, the set already holds the answer.

217. Contains Duplicate​

217

Contains Duplicate

LeetCode
Easy

Brute Force

FIG. 217 CONTAINS DUPLICATE ALL PAIRS● INTERACTIVE
visualization loads as you reach it
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
n = len(nums)
for i in range(n):
for j in range(n):
if i != j and nums[i] == nums[j]:
return True
return False
top ↑

Value to Index​

The same pass, but the map remembers where each value was, so the match can be reported as a pair of positions rather than a yes or no.

1. Two Sum​

1

Two Sum

LeetCode
Easy

Brute Force

FIG. 1 TWO SUM ALL PAIRS● INTERACTIVE
visualization loads as you reach it
class Solution:
def twoSum(self, nums: list[int], target: int) -> list[int]:
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]

Duplicates, collisions, and when sorting wins

Duplicates overwrite, collisions crowd: only crowding hurts. A duplicate key overwrites its own entry in O(1). A collision is two different keys in one bucket; enough of them make every operation O(n). Say it as: "Expected O(n), worst O(n2) under adversarial collisions."

When sorting beats the map. The map is O(n) expected. With adversarial collisions every lookup costs O(n), so its worst case is O(n2). Sorting guarantees O(n log n), the best worst case available here. The catch: LeetCode 1 returns original indices and sorting scrambles them, so sort (value, index) pairs (O(n) extra space), then run two pointers. Once the input arrives sorted (167), the sort is free and the map loses outright.

top ↑

167. Two Sum II - Input Array Is Sorted​

167

Two Sum II - Input Array Is Sorted

LeetCode
Medium

2 Converging Pointers

Borrowed from Two Pointers ↗
FIG. 167 TWO SUM II INPUT ARRAY IS SORTED● INTERACTIVE
visualization loads as you reach it
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total < target:
left += 1
elif total > target:
right -= 1
else:
return [left + 1, right + 1]
return [-1, -1]
top ↑

170. Two Sum III - Data structure design​

170

Two Sum III - Data structure design

LeetCode
Easy

Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value. Implement the TwoSum class: TwoSum() initializes with an empty array, void add(int number) adds number to the data structure, and boolean find(int value) returns true if there exists any pair of numbers whose sum is equal to value, otherwise false.

  • ["TwoSum", "add", "add", "add", "find", "find"] with [[], [1], [3], [5], [4], [7]] returns [null, null, null, null, true, false]: 1 + 3 = 4, and no pair sums to 7.
  • Constraints: -105 <= number <= 105, -231 <= value <= 231 - 1, at most 104 calls in total to add and find.

Set of Sums

FIG. 170 TWO SUM III SET OF SUMS● INTERACTIVE
visualization loads as you reach it
class TwoSum:
def __init__(self):
self.arr = []
self.totals = set()
 
def add(self, number: int) -> None:
for num in self.arr:
self.totals.add(num + number)
self.arr.append(number)
 
def find(self, value: int) -> bool:
return value in self.totals

Every approach

DesignaddfindSpace
Set of SumsO(n)O(1)O(n + min(n(n-1)/2, R))
Count MapO(1)O(d)O(d)
Sorted List + 2 Converging PointersO(log n + n)O(n)O(n)

Which one depends on whether add or find calls dominate.

top ↑

Canonical Key​

Sometimes the question is not "have I seen this value?" but "have I seen anything equivalent to this value?" Reduce each element to a canonical form - a form two equivalent elements always share - and use that as the key. The map then groups by equivalence without ever comparing two elements to each other.

eatteaateaetsortedone bucket
Otto sorts each word's letters into one canonical key, so eat, tea and ate all land in the same bucket.

49. Group Anagrams​

49

Group Anagrams

LeetCode
Medium

Sorted String Key

FIG. 49 GROUP ANAGRAMS SORTED KEY● INTERACTIVE
visualization loads as you reach it
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
hm = collections.defaultdict(list)
for s in strs:
hm[tuple(sorted(s))].append(s)
return list(hm.values())
top ↑

Bucketed Membership​

One value can be a member of several groups at once, and has to be unique inside every one of them. Keep a separate set per group and derive each group's index from the element's position, so a single pass asks every question it needs to about a cell before committing it.

36. Valid Sudoku​

36

Valid Sudoku

LeetCode
Medium

Sets per Row, Column and Box

FIG. 36 VALID SUDOKU SETS● INTERACTIVE
visualization loads as you reach it
class Solution:
def isValidSudoku(self, board: list[list[str]]) -> bool:
rows = collections.defaultdict(set)
cols = collections.defaultdict(set)
boxes = collections.defaultdict(set)
n = 9
for r in range(n):
for c in range(n):
cell = board[r][c]
if cell != ".":
b = 3 * (r // 3) + (c // 3)
if cell in rows[r] or cell in cols[c] or cell in boxes[b]:
return False
rows[r].add(cell)
cols[c].add(cell)
boxes[b].add(cell)
return True
top ↑

2133. Check if Every Row and Column Contains All Numbers​

2133

Check if Every Row and Column Contains All Numbers

LeetCode
Easy

One Set per Row and Column

FIG. 2133 CHECK VALID SETS● INTERACTIVE
visualization loads as you reach it
class Solution:
def checkValid(self, matrix: list[list[int]]) -> bool:
rows = collections.defaultdict(set)
cols = collections.defaultdict(set)
n = len(matrix)
for i in range(n):
for j in range(n):
cell = matrix[i][j]
rows[i].add(cell)
cols[j].add(cell)
for r in rows.values():
if len(r) != n:
return False
for c in cols.values():
if len(c) != n:
return False
return True
top ↑

Value to Cell​

When the input announces work by value but the question is asked about position, one prologue pass over the grid inverts it - every value becomes the coordinates of the single cell it names. The grid is then never read again, and the live pass is pure counting against that map.

2661. First Completely Painted Row or Column​

2661

First Completely Painted Row or Column

LeetCode
Medium

Map Values to Cells, Tally Rows and Columns

FIG. 2661 FIRST COMPLETE INDEX● INTERACTIVE
visualization loads as you reach it
class Solution:
def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
m, n = len(mat), len(mat[0])
hashmap = collections.defaultdict(tuple)
row = [0] * m
col = [0] * n
for i in range(m):
for j in range(n):
hashmap[mat[i][j]] = (i, j)
for idx, i in enumerate(arr):
r, c = hashmap[i]
row[r] += 1
col[c] += 1
if row[r] >= n or col[c] >= m:
return idx
return -1
top ↑

Sum to Count​

When the question is how many tuples hit a target, not which ones, split the tuple in half and store a count for every half-sum. A lookup of the negated half-sum then settles a whole group of tuples at once, and nothing needs deduping.

454. 4Sum II​

454

4Sum II

LeetCode
Medium

Meet in the Middle (2 + 2)

FIG. 454 4SUM II MEET IN THE MIDDLE● INTERACTIVE
visualization loads as you reach it
class Solution:
def fourSumCount(
self, nums1: list[int], nums2: list[int], nums3: list[int], nums4: list[int]
) -> int:
seen = collections.Counter()
ans = 0
for a in nums1:
for b in nums2:
seen[a + b] += 1
for c in nums3:
for d in nums4:
complement = -c - d
ans += seen[complement]
return ans

Every approach

ApproachTimeWhen an interviewer wants it
Aux space
Brute ForceO(n4)opening line
O(1)
Count one array (1 + 3)O(n3)"memory is tight"
O(n)
Meet in the Middle (2 + 2)O(n2)the expected answer
O(n2)
Sorted Pair Sums + 2 Converging PointersO(n2 log n)"no hashing"
O(n2)
Generalized kSum CountO(nk/2)"what about 6 arrays?"
O(nk/2)
top ↑

kSum Count​

kSum Count

Hard

Given k integer arrays arrays[0], ..., arrays[k - 1], each of length n, return the number of tuples (i_0, ..., i_{k-1}) such that arrays[0][i_0] + arrays[1][i_1] + ... + arrays[k-1][i_{k-1}] == 0.

This generalizes 454. 4Sum II from four arrays to any k. The solution below is written against the 4-array signature, and kSum(arrays) is the general part.

Example 1:

Input: k = 4, arrays = [[1, 2], [-2, -1], [-1, 2], [0, 2]]
Output: 2

Explanation: the two tuples are:

  1. (0, 0, 0, 1): 1 + (-2) + (-1) + 2 = 0
  2. (1, 1, 0, 0): 2 + (-1) + (-1) + 0 = 0

Example 2:

Input: k = 4, arrays = [[0], [0], [0], [0]]
Output: 1

Example 3:

Input: k = 3, arrays = [[1, -1], [1, -1], [1, -1]]
Output: 0

Explanation: every sum is an odd count of +1 and -1, so it is odd and never 0.

Constraints:

  • 1 <= k <= 6
  • 1 <= n <= 30
  • -228 <= arrays[i][j] <= 228
  • The answer fits in a 64-bit integer.

Meet in the Middle

class Solution:
def fourSumCount(
self, nums1: list[int], nums2: list[int], nums3: list[int], nums4: list[int]
) -> int:
def kSum(arrays):
def getCounter(arrays):
counter = collections.Counter()
for combo in itertools.product(*arrays):
counter[sum(combo)] += 1
return counter
 
half = len(arrays) // 2
left, right = getCounter(arrays[:half]), getCounter(arrays[half:])
ans = 0
for total, count in left.items():
ans += count * right[-total]
return ans
 
return kSum([nums1, nums2, nums3, nums4])
top ↑
On this page