Day 11: Array Manipulation & Hash Maps Pattern
Default to a hash map whenever a problem needs fast "have I seen this before?" lookups — turning O(n²) brute force into O(n).
Study
Concepts
Why hash maps turn O(n²) into O(n)
A huge class of array problems asks some version of "find a pair/element related to another element". The brute-force answer is a nested loop (O(n²)): for each element, scan the rest of the array. A hash map (JS `Map` or plain object) gives O(1) average lookup, so you can trade a second pass of looping for a single pass that reads-and-writes the map as it goes — O(n) time at the cost of O(n) space.
The trigger phrase to recognize this pattern in an interview: "find two numbers that...", "count frequency of...", "first non-repeating...", "group by...". Any of these should make you reach for a Map before anything else.
See It
Visualizations
Visualization
Two Sum with a hash map — one pass
For each number, check the map for its complement BEFORE inserting the current number.
Build It
Code Examples
Two Sum — brute force vs hash map
// Brute force: O(n^2) time, O(1) space
function twoSumBrute(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) return [i, j];
}
}
return [];
}
// Hash map: O(n) time, O(n) space
function twoSum(nums, target) {
const seen = new Map(); // value -> index
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (seen.has(complement)) return [seen.get(complement), i];
seen.set(nums[i], i);
}
return [];
}
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]Group Anagrams — hash map keyed by a canonical signature
function groupAnagrams(words) {
const groups = new Map(); // sorted-letters signature -> [words]
for (const word of words) {
const key = word.split('').sort().join('');
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(word);
}
return [...groups.values()];
}
console.log(groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']));
// [['eat','tea','ate'], ['tan','nat'], ['bat']]Remember
Key Takeaways
- Nested-loop O(n²) search problems almost always have an O(n) hash-map version — check the complement/target while looping once.
- Insert-after-check (check the map, THEN insert current element) avoids matching an element with itself.
- A Map key can be any canonical representation (sorted string, tuple string) to group "equivalent" items.
- Space/time tradeoff is explicit: you spend O(n) memory to save O(n) time — always mention this tradeoff out loud in interviews.
- JS Map preserves insertion order and allows any key type — prefer it over a plain object for non-string keys.
Do It
Practice
- 1Solve "First Unique Character in a String" using a frequency Map, in one pass to build it and one pass to find the answer.
- 2Solve "Subarray Sum Equals K" using a running-sum + hash map of prefix sums (not the two-pointer approach — it does not work with negatives).
- 3Time both the brute-force and hash-map Two Sum on a 10,000-element array with console.time to feel the difference.