Arrays & Hashing
Arrays and hash tables are the most fundamental data structures in programming. Hash maps provide O(1) average-time lookups, making them ideal for counting frequencies, detecting duplicates, and grouping related data. Mastering these patterns is essential because they appear in nearly every other algorithm topic.
When to Use
- →You need to count frequencies or occurrences of elements
- →You need O(1) lookups to check if an element exists
- →You need to group elements by some shared property
- →You need to find pairs or complements that satisfy a condition
- →You need to remove duplicates or detect them quickly
Approach
The core idea is to use a hash map (JavaScript object or Map) as an auxiliary data structure to store information as you iterate through the array. This trades space for time, turning O(n^2) brute-force solutions into O(n) single-pass algorithms.
For frequency counting, iterate through the array once, incrementing a counter in the map for each element. For complement/pair problems like Two Sum, store each element's index as you go and check if the needed complement already exists in the map. For grouping problems like Group Anagrams, derive a canonical key (e.g., sorted characters) and collect items sharing the same key.
A common optimization is bucket sort by frequency: create an array where the index represents frequency, then collect elements from the highest-frequency buckets. This gives O(n) time for "top K frequent" style problems without needing a heap.
Code Template
// Frequency counting pattern
function frequencyCount(arr) {
const map = new Map();
for (const item of arr) {
map.set(item, (map.get(item) || 0) + 1);
}
return map;
}
// Two Sum / complement lookup pattern
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 [];
}
// Grouping by key pattern
function groupByKey(items, keyFn) {
const groups = new Map();
for (const item of items) {
const key = keyFn(item);
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(item);
}
return [...groups.values()];
}