Arrays & Hash Map

One-liner: spend O(n) memory on a lookup table so that "have I seen this?" or "how many of these?" costs O(1) instead of another scan.

The analogy

A librarian has two ways to find a book. She can walk every shelf each time someone asks (slow), or she can keep a card catalogue that says exactly which shelf holds each title (fast). A hash map is that catalogue. You pay a little effort writing the card once, and every later question is a single glance.

Recognition signals

Reach for a hash map when you see any of these:

1. You keep asking "does X exist?" or "where did I see X?" while scanning, and a nested loop would answer it.
2. The input is unsorted and you may not reorder it (the answer needs original indices).
3. You need counts — how often does each value or letter occur?
4. Several items should land in the same bucket when they share some property (same letters, same remainder, same signature).
5. A brute force compares every pair, i.e. O(n²), and the second half of each pair can be computed from the first (a complement, a difference, a key).

Step-by-step walkthrough

Take Two Sum on [2, 7, 11, 15] with target 9:

1. Start with an empty map seen (value to index).
2. Read 2. Its complement is 9 - 2 = 7. Is 7 in seen? No. Remember 2 -> 0.
3. Read 7. Its complement is 2. Is 2 in seen? Yes, at index 0.
4. Answer: indices [0, 1].

Notice the order: ask first, remember second. That is what stops an element from pairing with itself.

Code template

Almost every lookup problem is this loop. What changes is the question you ask and what you store.

// lookupTemplate: one pass, asking the map "have I already seen what I need?"
// before remembering the current element.
func lookupTemplate(items []int, need func(int) int) (int, int, bool) {
	seen := map[int]int{} // value -> index where it was seen
	for i, v := range items {
		if j, ok := seen[need(v)]; ok { // 1. ask first
			return j, i, true
		}
		seen[v] = i // 2. remember after asking
	}
	return 0, 0, false
}

Why each part exists:

The real solution

// TwoSum: indices of the two numbers that add up to target.
// Remember each value's index; the complement is what we look up.
func TwoSum(nums []int, target int) []int {
	seen := map[int]int{}
	for i, v := range nums {
		if j, ok := seen[target-v]; ok {
			return []int{j, i}
		}
		seen[v] = i
	}
	return nil
}

Variations

Seen-set — only membership matters, so store nothing. map[int]struct{} is Go's idiomatic set:

// ContainsDuplicate: does any value appear at least twice?
// A map used as a set: struct{} stores nothing but membership.
func ContainsDuplicate(nums []int) bool {
	seen := map[int]struct{}{}
	for _, v := range nums {
		if _, ok := seen[v]; ok {
			return true
		}
		seen[v] = struct{}{}
	}
	return false
}

Frequency counting — build a count table. Letters from a fixed alphabet fit in a plain array, which is faster than a map:

// IsAnagram: same letters, same counts. Count up for s, down for t.
func IsAnagram(s, t string) bool {
	if len(s) != len(t) {
		return false
	}
	var count [26]int
	for i := 0; i < len(s); i++ {
		count[s[i]-'a']++
		count[t[i]-'a']--
	}
	for _, c := range count {
		if c != 0 {
			return false
		}
	}
	return true
}

Grouping by signature — give every item a canonical key and bucket by it. In Go an array like [26]int is comparable, so it can be a map key directly:

// GroupAnagrams: words with the same letter counts share a key.
func GroupAnagrams(words []string) [][]string {
	groups := map[[26]int][]string{} // arrays are comparable, so they can be keys
	for _, w := range words {
		var key [26]int
		for i := 0; i < len(w); i++ {
			key[w[i]-'a']++
		}
		groups[key] = append(groups[key], w)
	}
	out := make([][]string, 0, len(groups))
	for _, g := range groups {
		out = append(out, g)
	}
	return out
}

Count, then rank — the map does the counting; ranking is a separate step afterwards:

// TopKFrequent: count first, then pick the k most frequent values.
func TopKFrequent(nums []int, k int) []int {
	freq := map[int]int{}
	for _, v := range nums {
		freq[v]++
	}
	keys := make([]int, 0, len(freq))
	for v := range freq {
		keys = append(keys, v)
	}
	sort.Slice(keys, func(a, b int) bool {
		if freq[keys[a]] != freq[keys[b]] {
			return freq[keys[a]] > freq[keys[b]]
		}
		return keys[a] < keys[b]
	})
	if k > len(keys) {
		k = len(keys)
	}
	return keys[:k]
}

Complexity

Map operations are O(1) on average. You are buying speed with memory — always say that trade-off out loud in an interview.

Common mistakes

Practice ladder

Ordered Easy to Hard. Decide what you would store in the map, and what you would ask it, before coding.

1. 1.
   Two Sum

   What does the partner of nums[i] look like, and where could it be hiding?
   Easy
2. 2.
   Contains Duplicate
   Easy
3. 3.
   Valid Anagram

   Two strings are equal as multisets of letters.
   Easy
4. 4.
   Group Anagrams

   Find a key that is identical for every rearrangement.
   Medium
5. 5.
   Top K Frequent Elements

   Counting and ranking are two separate steps.
   Medium
6. 6.
   Subarray Sum Equals K

   What running quantity, if seen before, tells you a range sums to k?
   Medium
7. 7.
   Longest Consecutive Sequence

   You need O(n): which elements are the only sensible starting points?
   Medium
8. 8.
   First Missing Positive

   A lookup table is allowed, but could the array itself serve as one?
   Hard

Which pattern? Drills

Unlabeled problems — pick the pattern, then read why.