Arrays & Hash Maps

Arrays look things up by position in O(1), and hash maps look them up by value in O(1) on average. Most O(n) solutions use one or both.

BeginnerRead first: Big-O & Complexity

How It Works

An array stores its elements side by side in memory, so reading or writing nums[i] is O(1): the address is the start of the array plus i times the element size. Finding a value is another story. Without an order to exploit, you have to look at every element, which is O(n).

A hash map fixes that. It runs each key through a hash function that picks a bucket in an internal array, so inserting, finding or deleting a key takes O(1) on average. A hash set is the same structure with keys and no values. Replacing a scan with a hash lookup is the most common way to turn an O(n²) solution into an O(n) one.

put("cat", 3)   hash("cat") % 8 = 5
put("dog", 7)   hash("dog") % 8 = 2
put("cow", 1)   hash("cow") % 8 = 5   same bucket as "cat"

0 |
1 |
2 | "dog": 7
3 |
4 |
5 | "cat": 3 -> "cow": 1
6 |
7 |

A lookup hashes the key and checks one short bucket instead of the whole table. The hash values here are made up.

Collisions like cat and cow are normal, and they're why the O(1) is an average rather than a guarantee. The map keeps buckets short by growing its array and rehashing every key once it gets too full. Three patterns cover most problems:

Count things. Map each value to how many times it appears. Anagram checks, majority elements and first unique character problems are all counting problems.
Remember what you've seen. As you scan, store each value (with its index if you need it) so later elements can find their partner in O(1). That's Two Sum below.
Group by a key. Compute a key that equal items share, such as a word's sorted letters, and collect the items under it. That's Group Anagrams below.

Counting With a Hash Map, Step by Step

Step 1 of 8

nums

counts

Value being counted
Counted

Walk nums once and keep a count per value in the hash map counts. It starts empty.

3 isn't in counts yet, so its count reads as 0. Store 0 + 1 = 1 under the key 3.

1 is new too. A missing key counts as 0, so it gets its own row with 1.

3 is already a key with count 1. The hash finds it in O(1) on average, with no scan of the earlier values. Store 2.

2 is new too. A missing key counts as 0, so it gets its own row with 1.

1 is a key already, with count 1. Look it up, add one and store 2.

3 is a key already, with count 2. Look it up, add one and store 3.

One pass: 6 lookups and 6 stores. The map has no order, so sort by value before printing: [[1, 2], [2, 1], [3, 3]].

All 8 steps as text

Walk nums once and keep a count per value in the hash map counts. It starts empty.
3 isn't in counts yet, so its count reads as 0. Store 0 + 1 = 1 under the key 3.
1 is new too. A missing key counts as 0, so it gets its own row with 1.
3 is already a key with count 1. The hash finds it in O(1) on average, with no scan of the earlier values. Store 2.
2 is new too. A missing key counts as 0, so it gets its own row with 1.
1 is a key already, with count 1. Look it up, add one and store 2.
3 is a key already, with count 2. Look it up, add one and store 3.
One pass: 6 lookups and 6 stores. The map has no order, so sort by value before printing: [[1, 2], [2, 1], [3, 3]].

When to Reach for It

You need to know whether a value exists, or where its partner is, without scanning the array again.
The question is about how often things appear: duplicates, the most frequent item, the first unique one, or anything that appears at least k times.
Items have to be grouped by something they share, like the same letters or the same remainder.
Your brute force has an inner loop whose only job is to find one specific value.

Complexity

Operation	Time	Space
Read or write an array element by index	O(1)	O(1)
Search an unsorted array for a value	O(n)	O(1)
Insert or delete in the middle of an array	O(n), to shift the rest	O(1)
Hash map insert, lookup or delete	O(1) average, O(n) worst case	O(n) for n keys

The Template

Counting With a Hash Map

Walk the input once. For each value, look up its current count (zero if the value is new), add one and store it back. Each step is a lookup and a store, both O(1) on average, so counting n values is O(n), and the map holds one entry per distinct value.

A hash map's iteration order isn't sorted, and in Go it's deliberately random on every run. When the output has to be stable, as it does here, sort the entries before you print them. That sort is O(k log k) for k distinct values and isn't part of the counting itself.

Time O(n)Space O(k) for k distinct values

def count_frequencies(nums: list[int]) -> dict[int, int]:
    """How many times each value appears in `nums`."""
    counts: dict[int, int] = {}
    for num in nums:
        # A value that isn't in the map yet has been seen 0 times.
        counts[num] = counts.get(num, 0) + 1
    return counts


def sorted_counts(counts: dict[int, int]) -> list[list[int]]:
    """[value, count] pairs in ascending value order. A hash map's own order
    isn't sorted, so sort before printing to get the same output every run."""
    return [[value, count] for value, count in sorted(counts.items())]


if __name__ == "__main__":
    print(sorted_counts(count_frequencies([3, 1, 3, 2, 1, 3])))  # [[1, 2], [2, 1], [3, 3]]
    print(sorted_counts(count_frequencies([-2, 7, -2])))  # [[-2, 2], [7, 1]]
    print(sorted_counts(count_frequencies([])))  # []

// How many times each value appears in nums.
export function countFrequencies(nums: number[]): Map<number, number> {
  const counts = new Map<number, number>();
  for (const num of nums) {
    // A value that isn't in the map yet has been seen 0 times.
    counts.set(num, (counts.get(num) ?? 0) + 1);
  }
  return counts;
}

// [value, count] pairs in ascending value order. A hash map's own order
// isn't sorted, so sort before printing to get the same output every run.
function sortedCounts(counts: Map<number, number>): number[][] {
  return [...counts.entries()].sort((a, b) => a[0] - b[0]);
}

console.log(JSON.stringify(sortedCounts(countFrequencies([3, 1, 3, 2, 1, 3])))); // [[1,2],[2,1],[3,3]]
console.log(JSON.stringify(sortedCounts(countFrequencies([-2, 7, -2])))); // [[-2,2],[7,1]]
console.log(JSON.stringify(sortedCounts(countFrequencies([])))); // []

package main

import (
	"cmp"
	"fmt"
	"slices"
)

// countFrequencies returns how many times each value appears in nums.
func countFrequencies(nums []int) map[int]int {
	counts := map[int]int{}
	for _, num := range nums {
		// A value that isn't in the map yet has been seen 0 times.
		counts[num]++
	}
	return counts
}

// sortedCounts returns [value, count] pairs in ascending value order. A hash
// map's own order isn't sorted (Go even randomizes it), so sort before
// printing to get the same output every run.
func sortedCounts(counts map[int]int) [][2]int {
	pairs := [][2]int{}
	for value, count := range counts {
		pairs = append(pairs, [2]int{value, count})
	}
	slices.SortFunc(pairs, func(a, b [2]int) int { return cmp.Compare(a[0], b[0]) })
	return pairs
}

func main() {
	fmt.Println(sortedCounts(countFrequencies([]int{3, 1, 3, 2, 1, 3}))) // [[1 2] [2 1] [3 3]]
	fmt.Println(sortedCounts(countFrequencies([]int{-2, 7, -2})))        // [[-2 2] [7 1]]
	fmt.Println(sortedCounts(countFrequencies([]int{})))                 // []
}

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    // How many times each value appears in nums.
    public static Dictionary<int, int> CountFrequencies(int[] nums)
    {
        var counts = new Dictionary<int, int>();
        foreach (int num in nums)
        {
            // A value that isn't in the map yet has been seen 0 times.
            counts[num] = counts.GetValueOrDefault(num) + 1;
        }
        return counts;
    }

    // [value, count] pairs in ascending value order. A hash map's own order
    // isn't sorted, so sort before printing to get the same output every run.
    static List<int[]> SortedCounts(Dictionary<int, int> counts) =>
        counts.OrderBy(entry => entry.Key).Select(entry => new[] { entry.Key, entry.Value }).ToList();

    public static void Main()
    {
        Console.WriteLine(Format(SortedCounts(CountFrequencies(new[] { 3, 1, 3, 2, 1, 3 })))); // [[1, 2], [2, 1], [3, 3]]
        Console.WriteLine(Format(SortedCounts(CountFrequencies(new[] { -2, 7, -2 })))); // [[-2, 2], [7, 1]]
        Console.WriteLine(Format(SortedCounts(CountFrequencies(new int[0])))); // []
    }

    static string Format(List<int[]> pairs) =>
        "[" + string.Join(", ", pairs.Select(p => "[" + string.Join(", ", p) + "]")) + "]";
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    // How many times each value appears in nums.
    static Map<Integer, Integer> countFrequencies(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            // A value that isn't in the map yet has been seen 0 times.
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        return counts;
    }

    // [value, count] pairs in ascending value order. A hash map's own order
    // isn't sorted, so sort before printing to get the same output every run.
    static List<List<Integer>> sortedCounts(Map<Integer, Integer> counts) {
        List<List<Integer>> pairs = new ArrayList<>();
        for (var entry : counts.entrySet()) pairs.add(List.of(entry.getKey(), entry.getValue()));
        pairs.sort((a, b) -> Integer.compare(a.get(0), b.get(0)));
        return pairs;
    }

    public static void main(String[] args) {
        System.out.println(sortedCounts(countFrequencies(new int[] {3, 1, 3, 2, 1, 3}))); // [[1, 2], [2, 1], [3, 3]]
        System.out.println(sortedCounts(countFrequencies(new int[] {-2, 7, -2}))); // [[-2, 2], [7, 1]]
        System.out.println(sortedCounts(countFrequencies(new int[] {}))); // []
    }
}

Worked Problems

Each solution stays folded until you open it, so you can try the problem first. Every one is a complete program in Python, TypeScript, Go, C# and Java, run and checked against its expected output.

Two Sum

EASYLeetCode 1

Problem

Given an array nums and an integer target, return the indices of the two numbers that add up to target. Exactly one pair works, and you can't use the same element twice.

Example: nums = [2, 7, 11, 15] and target = 9 returns [0, 1], because nums[0] + nums[1] = 2 + 7 = 9.

Show Solution

Approach

The brute force tries every pair in O(n²). Flip the question instead: when you reach nums[i], the only value that completes it is target - nums[i]. Keep a map from each value you've already passed to its index, and ask the map whether that partner is in it.

Look up the partner before you store the current value. That way an element never pairs with itself, and duplicates still work: in [3, 3] with target 6, the second 3 finds the first one's index already in the map.

Two Sum, Step by Step

Step 1 of 6

nums

seen

Current value
Partner it needs
Passed, stored in seen
Answer

Find two values that add up to 6. When you reach nums[i], the only partner that works is 6 - nums[i], so ask seen for it.

6 - 3 = 3. Look first: seen is still empty, so this 3 can't pair with itself.

Now store 3 -> 0, so a later value that needs a 3 finds it in one lookup.

6 - 2 = 4, and seen has no 4. No value before this one completes it.

Now store 2 -> 1, so a later value that needs a 2 finds it in one lookup.

6 - 4 = 2, and seen has 2 at index 1. One lookup instead of a scan: return [1, 2].

All 6 steps as text

Find two values that add up to 6. When you reach nums[i], the only partner that works is 6 - nums[i], so ask seen for it.
6 - 3 = 3. Look first: seen is still empty, so this 3 can't pair with itself.
Now store 3 -> 0, so a later value that needs a 3 finds it in one lookup.
6 - 2 = 4, and seen has no 4. No value before this one completes it.
Now store 2 -> 1, so a later value that needs a 2 finds it in one lookup.
6 - 4 = 2, and seen has 2 at index 1. One lookup instead of a scan: return [1, 2].

Time O(n)Space O(n)

def two_sum(nums: list[int], target: int) -> list[int]:
    """Indices of the two numbers in `nums` that add up to `target`, or [-1, -1]."""
    seen: dict[int, int] = {}  # value -> index where we saw it
    for i, num in enumerate(nums):
        partner = target - num
        # Look before storing num, so an element can't pair with itself.
        if partner in seen:
            return [seen[partner], i]
        seen[num] = i
    return [-1, -1]


if __name__ == "__main__":
    print(two_sum([2, 7, 11, 15], 9))  # [0, 1]
    print(two_sum([3, 2, 4], 6))  # [1, 2]
    print(two_sum([3, 3], 6))  # [0, 1]

// Indices of the two numbers in nums that add up to target, or [-1, -1].
export function twoSum(nums: number[], target: number): [number, number] {
  const seen = new Map<number, number>(); // value -> index where we saw it
  for (let i = 0; i < nums.length; i++) {
    const partner = target - nums[i];
    // Look before storing nums[i], so an element can't pair with itself.
    const j = seen.get(partner);
    if (j !== undefined) return [j, i];
    seen.set(nums[i], i);
  }
  return [-1, -1];
}

console.log(JSON.stringify(twoSum([2, 7, 11, 15], 9))); // [0,1]
console.log(JSON.stringify(twoSum([3, 2, 4], 6))); // [1,2]
console.log(JSON.stringify(twoSum([3, 3], 6))); // [0,1]

package main

import "fmt"

// twoSum returns the indices of the two numbers in nums that add up to
// target, or [-1 -1].
func twoSum(nums []int, target int) [2]int {
	seen := map[int]int{} // value -> index where we saw it
	for i, num := range nums {
		partner := target - num
		// Look before storing num, so an element can't pair with itself.
		if j, ok := seen[partner]; ok {
			return [2]int{j, i}
		}
		seen[num] = i
	}
	return [2]int{-1, -1}
}

func main() {
	fmt.Println(twoSum([]int{2, 7, 11, 15}, 9)) // [0 1]
	fmt.Println(twoSum([]int{3, 2, 4}, 6))      // [1 2]
	fmt.Println(twoSum([]int{3, 3}, 6))         // [0 1]
}

using System;
using System.Collections.Generic;

public class Solution
{
    // Indices of the two numbers in nums that add up to target, or [-1, -1].
    public static int[] TwoSum(int[] nums, int target)
    {
        var seen = new Dictionary<int, int>(); // value -> index where we saw it
        for (int i = 0; i < nums.Length; i++)
        {
            int partner = target - nums[i];
            // Look before storing nums[i], so an element can't pair with itself.
            if (seen.TryGetValue(partner, out int j)) return new[] { j, i };
            seen[nums[i]] = i;
        }
        return new[] { -1, -1 };
    }

    public static void Main()
    {
        Console.WriteLine(Format(TwoSum(new[] { 2, 7, 11, 15 }, 9))); // [0, 1]
        Console.WriteLine(Format(TwoSum(new[] { 3, 2, 4 }, 6))); // [1, 2]
        Console.WriteLine(Format(TwoSum(new[] { 3, 3 }, 6))); // [0, 1]
    }

    static string Format(int[] values) => "[" + string.Join(", ", values) + "]";
}

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {
    // Indices of the two numbers in nums that add up to target, or [-1, -1].
    static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>(); // value -> index where we saw it
        for (int i = 0; i < nums.length; i++) {
            int partner = target - nums[i];
            // Look before storing nums[i], so an element can't pair with itself.
            Integer j = seen.get(partner);
            if (j != null) return new int[] {j, i};
            seen.put(nums[i], i);
        }
        return new int[] {-1, -1};
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(twoSum(new int[] {2, 7, 11, 15}, 9))); // [0, 1]
        System.out.println(Arrays.toString(twoSum(new int[] {3, 2, 4}, 6))); // [1, 2]
        System.out.println(Arrays.toString(twoSum(new int[] {3, 3}, 6))); // [0, 1]
    }
}

Group Anagrams

MEDIUMLeetCode 49

Problem

Given a list of lowercase words, group together the ones that are anagrams of each other, meaning they use exactly the same letters the same number of times. The groups can be returned in any order.

Example: ["eat", "tea", "tan", "ate", "nat", "bat"] groups into ["ate", "eat", "tea"], ["bat"] and ["nat", "tan"].

Show Solution

Approach

Two words are anagrams exactly when their sorted letters match: eat, tea and ate all sort to aet. Use the sorted word as the key in a map from key to list, and append each word to the list under its key. Every word with the same letters lands in the same list, and the map's values are the answer.

Sorting a word of length k costs O(k log k), so n words take O(n · k log k). You can get O(n · k) with a different key: count each of the 26 letters and use those counts as the key. The sorted key is shorter to write and fast enough for most interviews, so start there and mention the counting key as the follow-up.

The canonical helper isn't part of the algorithm. It sorts each group and then the groups by their first word, so all five languages print the same output even though their maps iterate in different orders.

Time O(n · k log k) for n words of length up to kSpace O(n · k)

def group_anagrams(words: list[str]) -> list[list[str]]:
    """Groups the words in `words` that are anagrams of each other."""
    groups: dict[str, list[str]] = {}  # sorted letters -> words
    for word in words:
        # Anagrams have the same letters, so sorting them gives the same key.
        key = "".join(sorted(word))
        groups.setdefault(key, []).append(word)
    return list(groups.values())


def canonical(groups: list[list[str]]) -> list[list[str]]:
    """Groups can come back in any order. Sort each group, then sort the groups
    by their first word, so every language prints the same answer."""
    return sorted((sorted(group) for group in groups), key=lambda group: group[0])


if __name__ == "__main__":
    print(canonical(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])))  # [['ate', 'eat', 'tea'], ['bat'], ['nat', 'tan']]
    print(canonical(group_anagrams(["a"])))  # [['a']]
    print(canonical(group_anagrams(["listen", "silent", "enlist", "google"])))  # [['enlist', 'listen', 'silent'], ['google']]

// Groups the words in words that are anagrams of each other.
export function groupAnagrams(words: string[]): string[][] {
  const groups = new Map<string, string[]>(); // sorted letters -> words
  for (const word of words) {
    // Anagrams have the same letters, so sorting them gives the same key.
    const key = [...word].sort().join("");
    const group = groups.get(key);
    if (group) group.push(word);
    else groups.set(key, [word]);
  }
  return [...groups.values()];
}

// Groups can come back in any order. Sort each group, then sort the groups by
// their first word, so every language prints the same answer.
function canonical(groups: string[][]): string[][] {
  for (const group of groups) group.sort();
  return groups.sort((a, b) => (a[0] < b[0] ? -1 : a[0] > b[0] ? 1 : 0));
}

console.log(JSON.stringify(canonical(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])))); // [["ate","eat","tea"],["bat"],["nat","tan"]]
console.log(JSON.stringify(canonical(groupAnagrams(["a"])))); // [["a"]]
console.log(JSON.stringify(canonical(groupAnagrams(["listen", "silent", "enlist", "google"])))); // [["enlist","listen","silent"],["google"]]

package main

import (
	"fmt"
	"slices"
	"strings"
)

// groupAnagrams groups the words in words that are anagrams of each other.
func groupAnagrams(words []string) [][]string {
	groups := map[string][]string{} // sorted letters -> words
	for _, word := range words {
		// Anagrams have the same letters, so sorting them gives the same key.
		letters := []byte(word)
		slices.Sort(letters)
		key := string(letters)
		groups[key] = append(groups[key], word)
	}
	result := [][]string{}
	for _, group := range groups {
		result = append(result, group)
	}
	return result
}

// canonical sorts each group, then sorts the groups by their first word.
// Groups can come back in any order, and this makes every language print the
// same answer.
func canonical(groups [][]string) [][]string {
	for _, group := range groups {
		slices.Sort(group)
	}
	slices.SortFunc(groups, func(a, b []string) int { return strings.Compare(a[0], b[0]) })
	return groups
}

func main() {
	fmt.Println(canonical(groupAnagrams([]string{"eat", "tea", "tan", "ate", "nat", "bat"}))) // [[ate eat tea] [bat] [nat tan]]
	fmt.Println(canonical(groupAnagrams([]string{"a"})))                                      // [[a]]
	fmt.Println(canonical(groupAnagrams([]string{"listen", "silent", "enlist", "google"})))   // [[enlist listen silent] [google]]
}

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    // Groups the words in words that are anagrams of each other.
    public static List<List<string>> GroupAnagrams(string[] words)
    {
        var groups = new Dictionary<string, List<string>>(); // sorted letters -> words
        foreach (string word in words)
        {
            // Anagrams have the same letters, so sorting them gives the same key.
            char[] letters = word.ToCharArray();
            Array.Sort(letters);
            string key = new string(letters);
            if (!groups.TryGetValue(key, out var group))
            {
                group = new List<string>();
                groups[key] = group;
            }
            group.Add(word);
        }
        return groups.Values.ToList();
    }

    // Groups can come back in any order. Sort each group, then sort the groups by
    // their first word, so every language prints the same answer. Ordinal
    // comparison sorts by character code, like the other languages do.
    static List<List<string>> Canonical(List<List<string>> groups)
    {
        foreach (var group in groups) group.Sort(StringComparer.Ordinal);
        groups.Sort((a, b) => string.CompareOrdinal(a[0], b[0]));
        return groups;
    }

    public static void Main()
    {
        Console.WriteLine(Format(Canonical(GroupAnagrams(new[] { "eat", "tea", "tan", "ate", "nat", "bat" })))); // [[ate, eat, tea], [bat], [nat, tan]]
        Console.WriteLine(Format(Canonical(GroupAnagrams(new[] { "a" })))); // [[a]]
        Console.WriteLine(Format(Canonical(GroupAnagrams(new[] { "listen", "silent", "enlist", "google" })))); // [[enlist, listen, silent], [google]]
    }

    static string Format(List<List<string>> groups) =>
        "[" + string.Join(", ", groups.Select(g => "[" + string.Join(", ", g) + "]")) + "]";
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    // Groups the words in words that are anagrams of each other.
    static List<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> groups = new HashMap<>(); // sorted letters -> words
        for (String word : words) {
            // Anagrams have the same letters, so sorting them gives the same key.
            char[] letters = word.toCharArray();
            Arrays.sort(letters);
            String key = new String(letters);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
        }
        return new ArrayList<>(groups.values());
    }

    // Groups can come back in any order. Sort each group, then sort the groups by
    // their first word, so every language prints the same answer.
    static List<List<String>> canonical(List<List<String>> groups) {
        for (List<String> group : groups) Collections.sort(group);
        groups.sort(Comparator.comparing(group -> group.get(0)));
        return groups;
    }

    public static void main(String[] args) {
        System.out.println(canonical(groupAnagrams(new String[] {"eat", "tea", "tan", "ate", "nat", "bat"}))); // [[ate, eat, tea], [bat], [nat, tan]]
        System.out.println(canonical(groupAnagrams(new String[] {"a"}))); // [[a]]
        System.out.println(canonical(groupAnagrams(new String[] {"listen", "silent", "enlist", "google"}))); // [[enlist, listen, silent], [google]]
    }
}

Common Pitfalls

Using an array as a key. Python won't hash a list at all, and in JavaScript, Java and C# two arrays with the same contents are different keys because they're compared by identity. Build a string or tuple key instead.
Expecting a map to come back in a particular order. Go randomizes it, and Java's HashMap and C#'s Dictionary make no promises. Sort the keys when the order matters.
Searching an array inside a loop with in, indexOf or contains. Each call is O(n), so the loop is O(n²). Put the values in a set first.
Storing the current element before looking for its partner in Two Sum. When target is twice nums[i], the element finds itself and you return the same index twice.
Treating hash operations as always O(1). That's the average. Hashing a string key costs time proportional to its length, and a poor hash can put every key in one bucket.