When to reach for a hash map
Ask: Am I trading space for a linear pass that would otherwise be nested loops? If yes, a hash map (or hash set) is usually the move. If the input is already sorted and you only need pairs of values — not original indices — prefer two pointers.
Analogy: coat check
A hash map is a coat check: you hand over a ticket and get your coat back fast. You don’t walk the whole closet. Collisions are two coats on one hook — you chain them or probe the next hook, but the average trip is still constant time.
Frequency maps
A frequency map answers “how many of X?” in O(1). Build it in one pass, then either query it (Valid Anagram, Top K) or grow/shrink it with a window (later lesson). In Python use Counter / defaultdict(int); in Java HashMap with merge or getOrDefault.
from collections import Counter
def is_anagram(s: str, t: str) -> bool:
"""Same multiset of characters ↔ equal frequency maps."""
return Counter(s) == Counter(t)
# Trace: s='anagram', t='nagaram' → both {a:3,n:1,g:1,r:1,m:1}boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] freq = new int[26]; // assume lowercase a–z; generalize with HashMap
for (int i = 0; i < s.length(); i++) {
freq[s.charAt(i) - 'a']++;
freq[t.charAt(i) - 'a']--;
}
for (int c : freq) if (c != 0) return false;
return true;
}
// Trace: s='anagram', t='nagaram' → all buckets end at 0The Two Sum family
Unsorted array, return indices of two numbers that add to target. Sorting would scramble indices, so store value → index as you scan. At each x, look up target - x.
def two_sum(nums, target):
seen = {} # value → index
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
return []
# nums=[2,7,11,15], target=9
# i=0: seen={2:0}
# i=1: need=2 → hit → [0,1]int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (seen.containsKey(need)) return new int[]{seen.get(need), i};
seen.put(nums[i], i);
}
return new int[]{};
}
// nums=[2,7,11,15], target=9 → [0,1]Prefix sums + hash map
Running prefix pref means “sum of nums[0..i]”. A subarray nums[j+1..i] sums to k iff pref[i] - pref[j] == k, i.e. you’ve seen prefix pref - k before. Count those prefixes in a map.
from collections import defaultdict
def subarray_sum_equals_k(nums, k):
seen = defaultdict(int)
seen[0] = 1 # empty prefix
pref = ans = 0
for x in nums:
pref += x
ans += seen[pref - k]
seen[pref] += 1
return ans
# nums=[1,2,3], k=3 → subarrays [1,2] and [3] → 2int subarraySum(int[] nums, int 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 → 2Sorting + two pointers crossover
Hash maps buy O(n) expected time with O(n) space. Sorting buys O(n log n) time with O(1)/O(log n) extra space and unlocks opposite-end two pointers. Know both stories.
- Need indices, unsorted → hash map (Two Sum I).
- Need values / pairs, space tight, ok to sort → sort + two pointers.
- Group by signature → sort each key (anagrams) or count-tuple as map key.
- Longest consecutive → hash set O(n), not sort O(n log n) — interviewers expect the set.
def two_sum_sorted(nums, target):
"""After sort: O(n) scan, O(1) extra. Loses original indices."""
a = sorted(nums)
lo, hi = 0, len(a) - 1
while lo < hi:
s = a[lo] + a[hi]
if s == target:
return True
if s < target:
lo += 1
else:
hi -= 1
return Falseboolean twoSumSorted(int[] nums, int target) {
int[] a = nums.clone();
Arrays.sort(a);
int lo = 0, hi = a.length - 1;
while (lo < hi) {
int s = a[lo] + a[hi];
if (s == target) return true;
if (s < target) lo++;
else hi--;
}
return false;
}Complexity — say it aloud
Space for time is the hash-map bargain. Name average vs worst-case if they push on hashing.
What a good explanation sounds like
You: ‘I’ll keep a map from value to index while I scan. At each nums[i] I look up target - nums[i]. If it’s present I’m done; otherwise I store the current value. One pass, O(n) time and space expected. If you needed constant extra space and sorting were allowed, I’d sort and use two pointers — but that loses original indices unless I track them.’
Pattern bank: more questions + efficient solutions
Six staples. For each: say the map/set key before you type. Python and Java solutions below are the efficient interview versions.
Q: Two Sum — given an integer array and a target, return indices of the two numbers that add up to target (exactly one solution; you may not use the same element twice).
def two_sum(nums, target):
seen = {}
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
return []
# O(n) time, O(n) spaceint[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (seen.containsKey(need)) return new int[]{seen.get(need), i};
seen.put(nums[i], i);
}
return new int[]{};
}
// O(n) time, O(n) spaceQ: Valid Anagram — given two strings s and t, return true if t is an anagram of s.
from collections import Counter
def is_anagram(s, t):
return Counter(s) == Counter(t)
# O(n) time, O(Σ) spaceboolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] freq = new int[26];
for (int i = 0; i < s.length(); i++) {
freq[s.charAt(i) - 'a']++;
freq[t.charAt(i) - 'a']--;
}
for (int c : freq) if (c != 0) return false;
return true;
}
// O(n) time, O(1) for fixed a–zQ: Group Anagrams — group an array of strings so that anagrams land in the same group.
from collections import defaultdict
def group_anagrams(strs):
groups = defaultdict(list)
for s in strs:
key = "".join(sorted(s)) # or tuple of 26 counts
groups[key].append(s)
return list(groups.values())
# O(n * L log L) with sort keysList<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> groups = new HashMap<>();
for (String s : strs) {
char[] ch = s.toCharArray();
Arrays.sort(ch);
String key = new String(ch);
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(groups.values());
}
// O(n * L log L) with sort keysQ: Top K Frequent Elements — return the k most frequent integers in the array (order among ties can vary).
from collections import Counter
def top_k_frequent(nums, k):
freq = Counter(nums)
# buckets[c] = values that appear c times
buckets = [[] for _ in range(len(nums) + 1)]
for val, c in freq.items():
buckets[c].append(val)
out = []
for c in range(len(buckets) - 1, 0, -1):
for val in buckets[c]:
out.append(val)
if len(out) == k:
return out
return out
# O(n) time, O(n) space (bucket)int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) freq.merge(x, 1, Integer::sum);
List<Integer>[] buckets = new List[nums.length + 1];
for (int i = 0; i < buckets.length; i++) buckets[i] = new ArrayList<>();
for (var e : freq.entrySet()) buckets[e.getValue()].add(e.getKey());
int[] out = new int[k];
int idx = 0;
for (int c = buckets.length - 1; c >= 1 && idx < k; c--) {
for (int val : buckets[c]) {
out[idx++] = val;
if (idx == k) return out;
}
}
return out;
}
// O(n) time, O(n) space (bucket)Q: Longest Consecutive Sequence — unsorted integers; return the length of the longest consecutive elements sequence. Must run in O(n) time.
def longest_consecutive(nums):
s = set(nums)
best = 0
for x in s:
if x - 1 in s:
continue # not a run head
length = 1
while x + length in s:
length += 1
best = max(best, length)
return best
# O(n) time, O(n) spaceint longestConsecutive(int[] nums) {
Set<Integer> s = new HashSet<>();
for (int x : nums) s.add(x);
int best = 0;
for (int x : s) {
if (s.contains(x - 1)) continue;
int length = 1;
while (s.contains(x + length)) length++;
best = Math.max(best, length);
}
return best;
}
// O(n) time, O(n) spaceQ: Product of Array Except Self — return an array answer where answer[i] is the product of all elements except nums[i]. O(n) time, no division, O(1) extra space excluding the output.
def product_except_self(nums):
n = len(nums)
out = [1] * n
left = 1
for i in range(n):
out[i] = left
left *= nums[i]
right = 1
for i in range(n - 1, -1, -1):
out[i] *= right
right *= nums[i]
return out
# O(n) time, O(1) extraint[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] out = new int[n];
int left = 1;
for (int i = 0; i < n; i++) {
out[i] = left;
left *= nums[i];
}
int right = 1;
for (int i = n - 1; i >= 0; i--) {
out[i] *= right;
right *= nums[i];
}
return out;
}
// O(n) time, O(1) extra