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.

217. Contains Duplicate​

Easy·
4 Approaches · 2 patterns
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

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​

Easy·
3 Approaches
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(n):
if i != j and nums[i] + nums[j] == target:
return [i, j]

167. Two Sum II - Input Array Is Sorted​

Medium·
3 Approaches · 3 patterns
FIG. 167 TWO SUM II INPUT ARRAY IS SORTED 3● INTERACTIVE
visualization loads as you reach it
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
"""Two Sum 1 solution"""
seen = collections.defaultdict(int)
for idx, num in enumerate(numbers):
complement = target - num
if complement in seen:
if seen[complement] != idx:
return [seen[complement] + 1, idx + 1]
seen[num] = idx

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.

49. Group Anagrams​

Medium·
2 Approaches
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())

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​

Medium·
2 Approaches
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

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

Easy·
2 Approaches
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

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​

Medium·
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