# Arrays & Hashing — Part 1: The Pattern

Arrays give O(1) access by index; hash maps and sets give O(1) average access **by value**. Most "easy" and many "medium" interview problems reduce to one idea: **replace a repeated search with a hash lookup**. If your brute force has a nested loop whose inner loop is *searching* for something, a hash map usually removes it.

![A brute-force nested search replaced by a single pass with a hash map](diagrams/01-hash-replaces-search.svg)

## 1. When to Reach for a Hash Map or Set

| You need to… | Use | Example |
|---|---|---|
| know whether you've seen a value before | **set** | contains duplicate, cycle detection |
| find the index or count of a value | **map value → index / count** | two sum, frequencies |
| group items that are "equivalent" | **map canonical key → list** | group anagrams |
| test membership many times | build a **set once**, then O(1) per query | longest consecutive sequence |
| count occurrences then pick the most common | **map + sort/heap/buckets** | top k frequent |

## 2. Four Recurring Techniques

1. **Seen set / complement lookup.** Walk once; for each element, check whether the value that would complete the answer is already stored.
2. **Frequency counting.** `Counter` in Python, a `Map` in JS/TS, a `Dictionary<T,int>` in C#. Two strings are anagrams exactly when their frequency maps are equal.
3. **Canonical keys.** Map every item to a normalized key (sorted letters, a tuple of counts, a normalized pattern), then group by that key.
4. **Prefix/suffix arrays.** Precompute running products or sums from both ends to answer "everything except i" in O(1) per index (covered further in `03-prefix_sums`).

## 3. Template: Group by a Canonical Key

The same skeleton solves "group anagrams", "group shifted strings" and "find duplicate files by content": compute a key, append to a bucket.

```typescript
function groupBySignature(words: string[]): string[][] {
  const groups = new Map<string, string[]>();
  for (const w of words) {
    const key = [...w].sort().join("");
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key)!.push(w);
  }
  return [...groups.values()];
}
```

```python
from collections import defaultdict

def group_by_signature(words):
    groups = defaultdict(list)          # signature -> words with that signature
    for w in words:
        key = "".join(sorted(w))         # canonical form: sorted letters
        groups[key].append(w)
    return list(groups.values())
```

**Complexity:** O(n · k log k) for n words of length k (sorting each word). Using a 26-letter count tuple as the key makes it O(n · k).

## 4. Choosing the Key Type

- **Python:** tuples are hashable, lists are not. Use `tuple(counts)` or `"".join(sorted(w))` as a key.
- **JavaScript/TypeScript:** `Map` keys compare by reference for objects/arrays, so **convert arrays to strings** (`counts.join("#")`). Plain objects coerce keys to strings, which is why `Map` is preferred for non-string keys.
- **C#:** `Dictionary<string, …>` works directly; for composite keys use a `record struct` or a value tuple `(int, int)`, which implement value equality.

## 5. Sets for O(1) Membership

Building a set costs O(n) once; afterwards each `in`/`has`/`Contains` is O(1) average. That turns "for each x, check whether x+1 exists" from O(n²) into O(n). This is the core of **Longest Consecutive Sequence** in Part 2.

## Under the Hood: Why Hash Lookups Are O(1) on Average

A hash table stores entries in an array of buckets; `hash(key) % capacity` picks the bucket. With a good hash function and a load factor kept below a threshold (≈0.66 in CPython's dict, 0.75 in Java/C#), each bucket holds O(1) entries on average, so lookups are O(1). When the table fills up it **resizes** (doubling the capacity and rehashing everything), which is why inserts are **amortized** O(1). The worst case is O(n), when many keys collide; this is why languages randomize string hashing (Python's `PYTHONHASHSEED`, .NET's randomized string hashing) to resist deliberately colliding inputs. See `languages/javascript/23-hashing_and_hash_tables` for the full mechanics.

## Common Pitfalls

1. **Using a list for membership tests** (`x in list`) inside a loop: O(n²).
2. **Mutable keys:** Python lists and JS arrays can't be used as value-based keys; convert to tuples/strings.
3. **Insert-before-check bugs** in complement lookups: with `[3, 3], target 6`, check for the complement *before* storing the current value.
4. **Forgetting that maps cost O(n) space**; mention it when you state complexity.
5. **Relying on dict ordering** in languages/versions where it isn't guaranteed (C# `Dictionary` enumeration order is not guaranteed).

## Quick Reference

```text
Repeated search inside a loop → hash map/set
seen = set();  if target - x in seen: …;  seen.add(x)
freq: Counter(s) · new Map() · Dictionary<char,int>
group: key = canonical(item); groups[key].append(item)
Time O(n) average · Space O(n)
```