Use hash maps and sets for O(1) lookups, frequency counting, and grouping.
A hash map stores key-value pairs with O(1) average-case get, put, and delete. A hash set stores unique keys. Hashing is the most common optimization in interview problems — it converts O(n²) brute-force pair searches into O(n) solutions by enabling instant lookups.
Get/Put/Delete O(1) average · O(n) worst case
O(n) to store n entries
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
Use this when the problem asks how many times each value appears
A hash map is ideal because you can update counts in one pass and then query those counts in O(1) average time. This is one of the most common interview optimizations because it removes repeated rescans of the same data.
Problem Top K Frequent Elements. Count the frequency of every number first, then use the counts to decide which values are most frequent.
function buildFrequency(nums) {
const freq = new Map();
for (const num of nums) {
freq.set(num, (freq.get(num) ?? 0) + 1);
}
return freq;
}
// Top K Frequent Elements
function topKFrequent(nums, k) {
const freq = buildFrequency(nums);
return [...freq.entries()]
.sort((a, b) => b[1] - a[1])
.slice(0, k)
.map(([num]) => num);
}Use this when you only care whether something has been seen before, not how many times it appears
A set keeps the code simpler than a map and makes duplicate detection very direct. This pattern is common in duplicate detection, cycle-style checks, and membership queries.
Problem Contains Duplicate. Scan the array once, and if a value is already in the set, you have found a duplicate immediately.
function containsDuplicate(nums) {
const seen = new Set();
for (const num of nums) {
if (seen.has(num)) return true;
seen.add(num);
}
return false;
}Use this when the answer for the current element depends on whether a matching partner has already appeared
Instead of trying every earlier element, store previously seen values in a hash map and query the needed complement instantly. This transforms many pair-search problems from O(n²) to O(n).
Problem Two Sum. For each number, compute target - nums[i]. If that value is already in the map, you have found the answer.
function twoSum(nums, target) {
const seen = new Map();
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 [];
}Use this when multiple items should belong together based on a normalized representation
Instead of comparing every pair, derive one key for each item and group items sharing that key. This pattern is especially powerful in anagram problems and category bucketing problems.
Problem Group Anagrams. Sort each word to create a stable signature, then collect words with the same signature in one list.
function groupAnagrams(strs) {
const groups = new Map();
for (const word of strs) {
const key = word.split('').sort().join('');
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(word);
}
return [...groups.values()];
}Use this when the answer depends on the history of running totals rather than raw elements
Store information about prefix sums in a map so each new position can instantly discover whether some earlier prefix creates a valid subarray. This pattern appears in subarray sum, longest balanced array, and modular remainder problems.
Problem Subarray Sum Equals K. Track the running sum, and whenever sum - k was seen earlier, add its frequency to the answer.
function subarraySum(nums, k) {
const freq = new Map([[0, 1]]);
let sum = 0, count = 0;
for (const num of nums) {
sum += num;
count += freq.get(sum - k) ?? 0;
freq.set(sum, (freq.get(sum) ?? 0) + 1);
}
return count;
}Use this concept to reason correctly about when hashing is the right tool
Hash maps and sets are O(1) on average, but poor hashing or adversarial input can degrade them. In interviews, you usually assume standard library hashing behaves well, but you should still know the trade-off.
Problem Design a frequency tracker. The main gain comes from constant-time average updates and lookups, which is why hashing is chosen over repeated linear scans.
// Average O(1) vs worst-case O(n) for hash maps
function frequencyTracker() {
const map = new Map();
return {
update(value) {
map.set(value, (map.get(value) ?? 0) + 1);
},
getCount(value) {
return map.get(value) ?? 0; // O(1) average
},
};
}