Three tools, three jobs
Prefix sums turn range sums into O(1) after O(n) build — and with a hash map unlock ‘subarray sum equals k’. Tries share prefixes for autocomplete. Matrices are graphs on a grid: bounds checks, visited marks, and a direction array prevent the usual bugs.
Analogy: running tally + shared prefixes
Prefix sums are a bartender’s running tally of the night’s sales: ask “how much between hour 2 and 5?” and subtract two numbers. A trie is a shared coat-rack of word prefixes — “app” and “apple” share the same starting hooks. A matrix is just a graph drawn on graph paper.
Prefix sums
from collections import defaultdict
def subarray_sum(nums, k):
pref = ans = 0; seen = defaultdict(int); seen[0]=1
for x in nums:
pref += x; ans += seen[pref-k]; seen[pref]+=1
return ansint subarraySum(int[] nums, int k) {
int pref = 0, ans = 0;
Map<Integer, Integer> seen = new HashMap<>();
seen.put(0, 1);
for (int x : nums) {
pref += x;
ans += seen.getOrDefault(pref - k, 0);
seen.merge(pref, 1, Integer::sum);
}
return ans;
}Tries
class Node:
def __init__(self):
self.child = {}; self.end = False
class Trie:
def __init__(self): self.root = Node()
def insert(self, w):
n = self.root
for c in w:
n = n.child.setdefault(c, Node())
n.end = Trueclass Node {
Map<Character, Node> child = new HashMap<>();
boolean end;
}
class Trie {
Node root = new Node();
void insert(String w) {
Node n = root;
for (char c : w.toCharArray()) {
n = n.child.computeIfAbsent(c, k -> new Node());
}
n.end = true;
}
}Matrices
- Islands / flood fill → DFS/BFS + visited
- Rotate / spiral → layer indexes
- Set zeroes → mark first row/col
Drill list
- Subarray sum equals k
- Range sum query
- Implement trie / prefix matching
- Number of islands
- Rotting oranges
- Set matrix zeroes
- Spiral / rotate image
When to reach for this pattern
Three tools, three jobs — don’t mix them. Prefix is arithmetic on arrays; trie is a tree on characters; matrices are 2D indexing discipline.
Core template + worked trace
Prefix sum + subarray sum equals k:
from collections import defaultdict
def subarray_sum(nums: list[int], k: int) -> int:
# count of prefixes; prefix[j] - prefix[i] = k ⇒ prefix[i] = prefix[j] - k
seen = defaultdict(int)
seen[0] = 1
pref = ans = 0
for x in nums:
pref += x
ans += seen[pref - k]
seen[pref] += 1
return ans
# nums=[1,2,3], k=3
# pref=1 seen{0:1,1:1}
# pref=3 → seen[0]=1 → ans=1 (subarray [1,2]); seen{0:1,1:1,3:1}
# pref=6 → seen[3]=1 → ans=2 (subarray [3])int subarraySum(int[] nums, int k) {
// count of prefixes; prefix[j] - prefix[i] = k ⇒ prefix[i] = prefix[j] - k
Map<Integer, Integer> seen = new HashMap<>();
seen.put(0, 1);
int pref = 0, ans = 0;
for (int x : nums) {
pref += x;
ans += seen.getOrDefault(pref - k, 0);
seen.merge(pref, 1, Integer::sum);
}
return ans;
}
// nums=[1,2,3], k=3
// pref=1 seen{0:1,1:1}
// pref=3 → seen[0]=1 → ans=1 (subarray [1,2]); seen{0:1,1:1,3:1}
// pref=6 → seen[3]=1 → ans=2 (subarray [3])Minimal trie insert / search:
class TrieNode:
def __init__(self):
self.children = {}
self.end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.end = True
def search(self, word: str) -> bool:
node = self.root
for ch in word:
if ch not in node.children:
return False
node = node.children[ch]
return node.endclass TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
boolean end;
}
class Trie {
TrieNode root = new TrieNode();
void insert(String word) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
node = node.children.computeIfAbsent(ch, k -> new TrieNode());
}
node.end = true;
}
boolean search(String word) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
if (!node.children.containsKey(ch)) return false;
node = node.children.get(ch);
}
return node.end;
}
}Edge cases & common bugs
Complexity — say it aloud
Interview talk track
You: ‘I’ll keep a running prefix and a map from prefix value to count. When I see prefix P, every earlier prefix P−k completes a subarray summing to k. For tries I’ll say each node is a character and end marks a complete word.’
Practice set
- Range Sum Query (immutable)
- Subarray Sum Equals K
- Contiguous Array (prefix 0/1 trick)
- Implement Trie (Prefix Tree)
- Word Search II (trie + DFS)
- Rotate Image
- Spiral Matrix
- Set Matrix Zeroes
Harder follow-up
Harder variant: Word Search II — insert all words into a trie, DFS the board while walking the trie, prune dead branches, mark visited cells. Speak pruning: ‘if this prefix isn’t in the trie, abandon the path.’
Pattern bank: more questions + efficient solutions
Prefix sums unlock range queries and subarray-sum counts; tries share string prefixes; grids are graphs with bounds checks.
Q: Subarray Sum Equals K — count continuous subarrays whose sum equals k.
from collections import defaultdict
def subarray_sum(nums, k):
freq = defaultdict(int); freq[0] = 1
p = ans = 0
for x in nums:
p += x
ans += freq[p - k]
freq[p] += 1
return ansint subarraySum(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
freq.put(0, 1);
int p = 0, ans = 0;
for (int x : nums) {
p += x;
ans += freq.getOrDefault(p - k, 0);
freq.merge(p, 1, Integer::sum);
}
return ans; // O(n)
}Q: Range Sum Query — Immutable — build so sumRange(l, r) is O(1).
class NumArray:
def __init__(self, nums):
self.pref = [0]
for x in nums:
self.pref.append(self.pref[-1] + x)
def sumRange(self, left, right):
return self.pref[right + 1] - self.pref[left]class NumArray {
private final int[] pref;
NumArray(int[] nums) {
pref = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) pref[i + 1] = pref[i] + nums[i];
}
int sumRange(int left, int right) { return pref[right + 1] - pref[left]; }
}Q: Implement Trie (Prefix Tree) — insert, search, startsWith.
class TrieNode:
def __init__(self):
self.child = {}
self.end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
n = self.root
for c in word:
n = n.child.setdefault(c, TrieNode())
n.end = True
def search(self, word):
n = self._walk(word)
return n is not None and n.end
def startsWith(self, prefix):
return self._walk(prefix) is not None
def _walk(self, s):
n = self.root
for c in s:
if c not in n.child: return None
n = n.child[c]
return nclass Trie {
static class Node {
Node[] next = new Node[26];
boolean end;
}
private final Node root = new Node();
void insert(String word) {
Node n = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (n.next[i] == null) n.next[i] = new Node();
n = n.next[i];
}
n.end = true;
}
boolean search(String word) {
Node n = walk(word); return n != null && n.end;
}
boolean startsWith(String prefix) { return walk(prefix) != null; }
private Node walk(String s) {
Node n = root;
for (char c : s.toCharArray()) {
int i = c - 'a';
if (n.next[i] == null) return null;
n = n.next[i];
}
return n;
}
}Q: Set Matrix Zeroes — if an element is 0, set its entire row and column to 0 in-place.
def set_zeroes(matrix):
m, n = len(matrix), len(matrix[0])
row0 = any(matrix[0][j] == 0 for j in range(n))
col0 = any(matrix[i][0] == 0 for i in range(m))
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = matrix[0][j] = 0
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if row0:
for j in range(n): matrix[0][j] = 0
if col0:
for i in range(m): matrix[i][0] = 0void setZeroes(int[][] a) {
int m = a.length, n = a[0].length;
boolean row0 = false, col0 = false;
for (int j = 0; j < n; j++) if (a[0][j] == 0) row0 = true;
for (int i = 0; i < m; i++) if (a[i][0] == 0) col0 = true;
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
if (a[i][j] == 0) { a[i][0] = 0; a[0][j] = 0; }
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
if (a[i][0] == 0 || a[0][j] == 0) a[i][j] = 0;
if (row0) for (int j = 0; j < n; j++) a[0][j] = 0;
if (col0) for (int i = 0; i < m; i++) a[i][0] = 0;
}Q: Rotting Oranges — each minute, rotten oranges infect 4-adjacent fresh. Minutes until all rotten, or -1.
from collections import deque
def oranges_rotting(grid):
m, n = len(grid), len(grid[0])
q, fresh = deque(), 0
for i in range(m):
for j in range(n):
if grid[i][j] == 2: q.append((i, j))
elif grid[i][j] == 1: fresh += 1
mins = 0
while q and fresh:
for _ in range(len(q)):
i, j = q.popleft()
for di, dj in ((0,1),(0,-1),(1,0),(-1,0)):
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
grid[ni][nj] = 2; fresh -= 1; q.append((ni, nj))
mins += 1
return mins if fresh == 0 else -1int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length, fresh = 0;
ArrayDeque<int[]> q = new ArrayDeque<>();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) q.add(new int[]{i, j});
else if (grid[i][j] == 1) fresh++;
}
int mins = 0;
int[][] d = {{0,1},{0,-1},{1,0},{-1,0}};
while (!q.isEmpty() && fresh > 0) {
for (int sz = q.size(); sz > 0; sz--) {
int[] c = q.poll();
for (int[] dir : d) {
int ni = c[0] + dir[0], nj = c[1] + dir[1];
if (ni < 0 || nj < 0 || ni >= m || nj >= n || grid[ni][nj] != 1) continue;
grid[ni][nj] = 2; fresh--; q.add(new int[]{ni, nj});
}
}
mins++;
}
return fresh == 0 ? mins : -1; // O(mn)
}