Hash Tables

A good hash function should:

• Deterministic: Same key always produces the same hash.
• Uniform distribution: Keys spread evenly across buckets to minimize collisions.
• Fast computation: O(1) for fixed-length keys.
• Minimize collisions: Different keys should ideally produce different hashes.

// Simple hash function for strings
function simpleHash(key, tableSize) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
        hash = (hash * 31 + key.charCodeAt(i)) % tableSize;
    }
    return hash;
}
// simpleHash("hello", 100) => some index 0-99

Multiplying by a prime (31) helps distribute keys more uniformly.

Chaining: Each bucket holds a linked list. Colliding keys are stored in the same bucket's list.

Open Addressing: On collision, probe for the next available slot (linear probing, quadratic probing, or double hashing).

// Chaining example
class HashTableChaining {
    constructor(size = 53) {
        this.table = new Array(size).fill(null).map(() => []);
    }
    _hash(key) {
        let h = 0;
        for (const ch of String(key)) h = (h * 31 + ch.charCodeAt(0)) % this.table.length;
        return h;
    }
    set(key, val) {
        const idx = this._hash(key);
        const existing = this.table[idx].find(p => p[0] === key);
        if (existing) existing[1] = val;
        else this.table[idx].push([key, val]);
    }
    get(key) {
        const pair = this.table[this._hash(key)].find(p => p[0] === key);
        return pair ? pair[1] : undefined;
    }
}

Chaining is simpler; open addressing has better cache performance.

Hash map (hash table) operation complexities:

• Insert (set): O(1) average, O(n) worst case
• Lookup (get): O(1) average, O(n) worst case
• Delete: O(1) average, O(n) worst case
• Space: O(n)

Worst case occurs when all keys hash to the same bucket. A good hash function and a proper load factor (typically < 0.75) keep operations near O(1).

// Load factor = number of entries / number of buckets
// When load factor exceeds threshold, the table is resized
// (usually doubled) and all entries are rehashed.

JavaScript's Map and Object handle this automatically.

Store each number's index in a hash map. For each element, check if target - num already exists in the map.

function twoSum(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
    return [];
}
// twoSum([2, 7, 11, 15], 9) => [0, 1]
// twoSum([3, 3], 6) => [0, 1]

Time: O(n)  |  Space: O(n). Much better than the brute-force O(n²) approach.

Use sorted characters as the key. All anagrams produce the same sorted key.

function groupAnagrams(strs) {
    const map = new Map();
    for (const str of strs) {
        const key = str.split('').sort().join('');
        if (!map.has(key)) map.set(key, []);
        map.get(key).push(str);
    }
    return Array.from(map.values());
}
// groupAnagrams(["eat","tea","tan","ate","nat","bat"])
// => [["eat","tea","ate"], ["tan","nat"], ["bat"]]

Time: O(n × k log k) where k is the max string length  |  Space: O(n × k)

Iterate through the array and add each element to a set. The first element already in the set is the first duplicate.

function firstDuplicate(arr) {
    const seen = new Set();
    for (const num of arr) {
        if (seen.has(num)) return num;
        seen.add(num);
    }
    return -1; // no duplicate
}
// firstDuplicate([2, 1, 3, 5, 3, 2]) => 3
// firstDuplicate([1, 2, 3]) => -1

Time: O(n)  |  Space: O(n)

Iterate through the collection and increment counts in a Map (or object).

function countFrequency(arr) {
    const freq = new Map();
    for (const item of arr) {
        freq.set(item, (freq.get(item) || 0) + 1);
    }
    return freq;
}
// countFrequency([1,2,2,3,3,3])
// => Map { 1 => 1, 2 => 2, 3 => 3 }

// Find element with highest frequency:
function mostFrequent(arr) {
    const freq = countFrequency(arr);
    let maxItem, maxCount = 0;
    for (const [item, count] of freq) {
        if (count > maxCount) { maxCount = count; maxItem = item; }
    }
    return maxItem;
}

Time: O(n)  |  Space: O(k) where k is the number of unique elements.

Put the first array into a Set, then filter the second array to keep only elements present in the Set.

function intersection(arr1, arr2) {
    const set = new Set(arr1);
    return [...new Set(arr2.filter(x => set.has(x)))];
}
// intersection([1,2,2,1], [2,2]) => [2]
// intersection([4,9,5], [9,4,9,8,4]) => [9, 4]

// For intersection with duplicates:
function intersect(arr1, arr2) {
    const map = new Map();
    for (const n of arr1) map.set(n, (map.get(n) || 0) + 1);
    const result = [];
    for (const n of arr2) {
        if (map.get(n) > 0) { result.push(n); map.set(n, map.get(n) - 1); }
    }
    return result;
}

Time: O(n + m)  |  Space: O(n)

An LRU (Least Recently Used) Cache evicts the least recently accessed item when capacity is full. It combines a hash map (for O(1) lookup) and a doubly linked list (for O(1) insertion/removal).

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
    }

    get(key) {
        if (!this.cache.has(key)) return -1;
        const val = this.cache.get(key);
        this.cache.delete(key);     // remove
        this.cache.set(key, val);   // re-insert (most recent)
        return val;
    }

    put(key, value) {
        if (this.cache.has(key)) this.cache.delete(key);
        this.cache.set(key, value);
        if (this.cache.size > this.capacity) {
            // Delete the least recently used (first inserted)
            const oldest = this.cache.keys().next().value;
            this.cache.delete(oldest);
        }
    }
}

JavaScript's Map preserves insertion order, making this implementation simple. All operations are O(1).

Use a hash map to store each number's complement (target - num). For each element, check if it already exists in the map.

function twoSum(nums, target) {
    const map = new Map(); // value -> index
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) return [map.get(complement), i];
        map.set(nums[i], i);
    }
    return [];
}
// Input: nums=[2,7,11,15], target=9   => Output: [0,1]
// Input: nums=[3,2,4], target=6       => Output: [1,2]
// Input: nums=[3,3], target=6         => Output: [0,1]

Time: O(n)  |  Space: O(n)

Use a prefix sum hash map. Count occurrences of (prefixSum - k) as you scan: each match means a subarray ending here sums to k.

function subarraySum(nums, k) {
    const map = new Map([[0, 1]]); // prefixSum -> count
    let sum = 0, count = 0;
    for (const num of nums) {
        sum += num;
        count += map.get(sum - k) || 0;
        map.set(sum, (map.get(sum) || 0) + 1);
    }
    return count;
}
// Input: nums=[1,1,1], k=2       => Output: 2
// Input: nums=[1,2,3], k=3       => Output: 2   ([1,2] and [3])
// Input: nums=[-1,-1,1], k=0     => Output: 1

Time: O(n)  |  Space: O(n)

A string can form a palindrome if at most one character has an odd frequency. Use a Set to toggle character presence.

function canPermutePalindrome(s) {
    const set = new Set();
    for (const ch of s) {
        if (set.has(ch)) set.delete(ch); // even count: remove
        else set.add(ch);               // odd count: add
    }
    return set.size <= 1; // at most one odd-frequency char
}
// Input: "aab"       => Output: true  ("aba" is palindrome)
// Input: "code"      => Output: false
// Input: "carerac"   => Output: true  ("racecar")

Time: O(n)  |  Space: O(k) unique chars

Put all numbers in a Set. Only start counting from elements where num - 1 is NOT in the set (start of a sequence). Track the longest streak.

function longestConsecutive(nums) {
    const set = new Set(nums);
    let best = 0;
    for (const num of set) {
        if (!set.has(num - 1)) { // start of a sequence
            let len = 1;
            while (set.has(num + len)) len++;
            best = Math.max(best, len);
        }
    }
    return best;
}
// Input: [100,4,200,1,3,2]     => Output: 4   (1,2,3,4)
// Input: [0,3,7,2,5,8,4,6,0,1] => Output: 9
// Input: []                    => Output: 0

Time: O(n)  |  Space: O(n)

Use a Set and scan left to right. The first number already in the set is the answer.

function firstDuplicate(arr) {
    const seen = new Set();
    for (const num of arr) {
        if (seen.has(num)) return num;
        seen.add(num);
    }
    return -1;
}
// Input: [2,1,3,5,3,2]   => Output: 3  (3 appears at index 2 and 4)
// Input: [2,4,3,5,1]     => Output: -1 (no duplicates)
// Input: [1,1]           => Output: 1

Time: O(n)  |  Space: O(n)

Split the string on whitespace, then use a Map to tally each word's count.

function wordFrequency(sentence) {
    const freq = new Map();
    for (const word of sentence.toLowerCase().split(/s+/)) {
        freq.set(word, (freq.get(word) || 0) + 1);
    }
    return freq;
}
// Input: "the sky is blue the sky"
// Output: Map { 'the' => 2, 'sky' => 2, 'is' => 1, 'blue' => 1 }

// Input: "hello world hello"
// Output: Map { 'hello' => 2, 'world' => 1 }

Time: O(n)  |  Space: O(k) unique words

Parse each path, extract content, and use a Map from content to list of paths. Return groups with 2+ paths.

function findDuplicate(paths) {
    const map = new Map();
    for (const path of paths) {
        const parts = path.split(' ');
        const dir = parts[0];
        for (let i = 1; i < parts.length; i++) {
            const bracketIdx = parts[i].indexOf('(');
            const filename = parts[i].slice(0, bracketIdx);
            const content  = parts[i].slice(bracketIdx + 1, parts[i].length - 1);
            const fullPath = dir + '/' + filename;
            if (!map.has(content)) map.set(content, []);
            map.get(content).push(fullPath);
        }
    }
    return [...map.values()].filter(group => group.length > 1);
}
// Input: ["root/a 1.txt(abcd) 2.txt(efgh)", "root/b 4.txt(abcd)"]
// Output: [["root/a/1.txt","root/b/4.txt"]]

Time: O(n × m) average  |  Space: O(n × m)

Sort the array, then use two outer loops + two-pointer technique for the inner pair. Use a Set to deduplicate results easily.

function fourSum(nums, target) {
    nums.sort((a, b) => a - b);
    const result = [];
    for (let i = 0; i < nums.length - 3; i++) {
        if (i > 0 && nums[i] === nums[i-1]) continue; // skip duplicates
        for (let j = i + 1; j < nums.length - 2; j++) {
            if (j > i+1 && nums[j] === nums[j-1]) continue;
            let l = j + 1, r = nums.length - 1;
            while (l < r) {
                const sum = nums[i] + nums[j] + nums[l] + nums[r];
                if (sum === target) {
                    result.push([nums[i], nums[j], nums[l], nums[r]]);
                    while (l < r && nums[l] === nums[l+1]) l++;
                    while (l < r && nums[r] === nums[r-1]) r--;
                    l++; r--;
                } else if (sum < target) l++;
                else r--;
            }
        }
    }
    return result;
}
// Input: nums=[1,0,-1,0,-2,2], target=0
// Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Time: O(n³)  |  Space: O(1) excluding output

Use an array of buckets with separate chaining (linked list or array per bucket). The hash function maps a key to a bucket index.

class HashMap {
    constructor(size = 1000) {
        this.buckets = new Array(size).fill(null).map(() => []);
        this.size = size;
    }
    _hash(key) {
        let hash = 0;
        for (const ch of String(key)) hash = (hash * 31 + ch.charCodeAt(0)) % this.size;
        return hash;
    }
    set(key, value) {
        const bucket = this.buckets[this._hash(key)];
        const pair = bucket.find(p => p[0] === key);
        if (pair) pair[1] = value;
        else bucket.push([key, value]);
    }
    get(key) {
        const pair = this.buckets[this._hash(key)].find(p => p[0] === key);
        return pair ? pair[1] : undefined;
    }
    delete(key) {
        const idx = this._hash(key);
        this.buckets[idx] = this.buckets[idx].filter(p => p[0] !== key);
    }
}
// set("a",1), set("b",2), get("a") => 1, delete("a"), get("a") => undefined

Average Time: O(1) per op | Worst (all collide): O(n)  |  Space: O(n)

Build a frequency map, then either find the max in O(n) or use a bucket sort approach for a full frequency ranking.

function topKFrequent(nums, k) {
    const freq = new Map();
    for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
    // Bucket sort: index = frequency
    const buckets = new Array(nums.length + 1).fill(null).map(() => []);
    for (const [num, count] of freq) buckets[count].push(num);
    const result = [];
    for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
        result.push(...buckets[i]);
    }
    return result.slice(0, k);
}
// Input: nums=[1,1,1,2,2,3], k=2   => Output: [1,2]
// Input: nums=[1], k=1             => Output: [1]

Time: O(n) bucket sort  |  Space: O(n)

For an undirected graph, use DFS with a visited set. If you visit a node that's already in the current path (recursion stack), a cycle exists.

function hasCycle(numNodes, edges) {
    const adj = Array.from({length: numNodes}, () => []);
    for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
    const visited = new Set();
    function dfs(node, parent) {
        visited.add(node);
        for (const neighbor of adj[node]) {
            if (!visited.has(neighbor)) {
                if (dfs(neighbor, node)) return true;
            } else if (neighbor !== parent) {
                return true; // back edge = cycle
            }
        }
        return false;
    }
    for (let i = 0; i < numNodes; i++) {
        if (!visited.has(i) && dfs(i, -1)) return true;
    }
    return false;
}
// Input: 4 nodes, edges=[[0,1],[1,2],[2,3],[3,0]]  => Output: true
// Input: 4 nodes, edges=[[0,1],[0,2],[1,3]]         => Output: false

Time: O(V + E)  |  Space: O(V)

Calculate net balance for each person using a map. Then greedily match the person with maximum debt against the person with maximum credit.

function minTransfers(transactions) {
    const balance = new Map();
    for (const [from, to, amount] of transactions) {
        balance.set(from, (balance.get(from) || 0) - amount);
        balance.set(to,   (balance.get(to)   || 0) + amount);
    }
    const debts = [...balance.values()].filter(v => v !== 0);
    function settle(k) {
        while (k < debts.length && debts[k] === 0) k++;
        if (k === debts.length) return 0;
        let min = Infinity;
        for (let i = k + 1; i < debts.length; i++) {
            if (debts[k] * debts[i] < 0) { // opposite signs
                debts[i] += debts[k];
                min = Math.min(min, 1 + settle(k + 1));
                debts[i] -= debts[k]; // backtrack
            }
        }
        return min;
    }
    return settle(0);
}
// Input: [[0,1,10],[2,0,5]]     => Output: 2
// Input: [[0,1,10],[1,0,1],[1,2,5],[2,0,5]] => Output: 1

Time: O(n!) worst case  |  Space: O(n)

Generate all substrings and insert them into a Set to automatically deduplicate. Return the set's size.

function countDistinctSubstrings(s) {
    const set = new Set();
    for (let i = 0; i < s.length; i++) {
        for (let j = i + 1; j <= s.length; j++) {
            set.add(s.slice(i, j));
        }
    }
    return set.size;
}
// Input: "abc"   => Output: 6  ("a","b","c","ab","bc","abc")
// Input: "aaa"   => Output: 3  ("a","aa","aaa")
// Input: "abab"  => Output: 7

Time: O(n³) due to string creation  |  Space: O(n²)

For larger inputs, use Trie or Suffix Array for O(n²) or O(n log n).