Arrays & Hashing

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.

1When to Reach for a Hash Map or Set

2Four 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).

3Template: 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.

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()];
}

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).

4Choosing 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.

5Sets 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.

⚠️ 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

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)

Six classic problems in increasing difficulty. Try each one for 15–20 minutes before reading the approach.

1Contains Duplicate (LeetCode 217)

🟢 Easy. Return true if any value appears at least twice in nums, otherwise false.

nums = [1,2,3,1] → true
nums = [1,2,3,4] → false

Approach. Insert each number into a set; if it's already there, you've found a duplicate. (Sorting and comparing neighbours also works in O(n log n) time and O(1) extra space.)

Complexity. O(n) time, O(n) space.

function containsDuplicate(nums: number[]): boolean {
  const seen = new Set<number>();
  for (const x of nums) {
    if (seen.has(x)) return true;
    seen.add(x);
  }
  return false;
}

def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

2Valid Anagram (LeetCode 242)

🟢 Easy. Given strings s and t, return true if t is an anagram of s (same letters, same counts).

s = "anagram", t = "nagaram" → true

Approach. Different lengths → false immediately. Otherwise count letters of s up and letters of t down; every count must end at zero.

Complexity. O(n) time, O(1) space for a fixed alphabet (O(k) for k distinct characters).

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;
  const counts = new Map<string, number>();
  for (let i = 0; i < s.length; i++) {
    counts.set(s[i], (counts.get(s[i]) ?? 0) + 1);
    counts.set(t[i], (counts.get(t[i]) ?? 0) - 1);
  }
  for (const v of counts.values()) if (v !== 0) return false;
  return true;
}

def is_anagram(s, t):
    if len(s) != len(t):
        return False
    counts = {}
    for a, b in zip(s, t):
        counts[a] = counts.get(a, 0) + 1
        counts[b] = counts.get(b, 0) - 1
    return all(v == 0 for v in counts.values())

3Group Anagrams (LeetCode 49)

🟠 Medium. Group the strings in strs so that anagrams are together. Any order is accepted.

strs = ["eat","tea","tan","ate","nat","bat"]
→ [["bat"],["nat","tan"],["ate","eat","tea"]]

Approach. Use a canonical key per word. Sorting the letters gives O(k log k) per word; a 26-slot count tuple gives O(k). Append each word to the bucket for its key.

Complexity. O(n·k) time with count keys, O(n·k) space.

function groupAnagrams(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();
  for (const w of strs) {
    const counts = new Array(26).fill(0);
    for (const c of w) counts[c.charCodeAt(0) - 97]++;
    const key = counts.join("#");
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key)!.push(w);
  }
  return [...groups.values()];
}

from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)
    for w in strs:
        counts = [0] * 26
        for c in w:
            counts[ord(c) - 97] += 1
        groups[tuple(counts)].append(w)
    return list(groups.values())

4Top K Frequent Elements (LeetCode 347)

🟠 Medium. Return the k most frequent elements of nums. The answer is unique; any order.

nums = [1,1,1,2,2,3], k = 2 → [1,2]

Approach. Count frequencies, then bucket sort by frequency: buckets[f] holds the numbers that occur f times (f ≤ n). Walk buckets from high to low until you have k numbers. A size-k heap gives O(n log k) and is the more general answer; buckets give O(n).

Complexity. O(n) time with buckets, O(n) space.

function topKFrequent(nums: number[], k: number): number[] {
  const counts = new Map<number, number>();
  for (const x of nums) counts.set(x, (counts.get(x) ?? 0) + 1);
  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
  for (const [x, f] of counts) buckets[f].push(x);
  const result: number[] = [];
  for (let f = buckets.length - 1; f > 0 && result.length < k; f--) {
    for (const x of buckets[f]) {
      result.push(x);
      if (result.length === k) break;
    }
  }
  return result;
}

def top_k_frequent(nums, k):
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
    buckets = [[] for _ in range(len(nums) + 1)]
    for x, f in counts.items():
        buckets[f].append(x)
    result = []
    for f in range(len(buckets) - 1, 0, -1):
        for x in buckets[f]:
            result.append(x)
            if len(result) == k:
                return result
    return result

5Product of Array Except Self (LeetCode 238)

🟠 Medium. Return answer where answer[i] is the product of all elements except nums[i], in O(n) time without division.

nums = [1,2,3,4] → [24,12,8,6]

Approach. answer[i] = (product of everything left of i) × (product of everything right of i). First pass left→right writes the prefix products into answer; second pass right→left multiplies in a running suffix product.

Complexity. O(n) time, O(1) extra space (the output array doesn't count).

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const answer = new Array(n).fill(1);
  let prefix = 1;
  for (let i = 0; i < n; i++) { answer[i] = prefix; prefix *= nums[i]; }
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) { answer[i] *= suffix; suffix *= nums[i]; }
  return answer;
}

def product_except_self(nums):
    n = len(nums)
    answer = [1] * n
    prefix = 1
    for i in range(n):
        answer[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= suffix
        suffix *= nums[i]
    return answer

6Longest Consecutive Sequence (LeetCode 128)

🟠 Medium. Return the length of the longest run of consecutive integers in an unsorted array, in O(n) time.

nums = [100,4,200,1,3,2] → 4   (1,2,3,4)

Approach. Put everything in a set. A number starts a run only if x − 1 is not in the set; from each start, count upward while x + 1 exists. Every number is visited at most twice (once as a candidate, once inside a run), so the total is O(n), even though there's a nested loop.

Complexity. O(n) time, O(n) space.

function longestConsecutive(nums: number[]): number {
  const s = new Set(nums);
  let best = 0;
  for (const x of s) {
    if (s.has(x - 1)) continue;          // not a run start
    let length = 1;
    while (s.has(x + length)) length++;
    best = Math.max(best, length);
  }
  return best;
}

def longest_consecutive(nums):
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 not in s:              # x starts a run
            length = 1
            while x + length in s:
                length += 1
            best = max(best, length)
    return best

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

✅ Check yourself

Source: algo_arrays_and_hashing_theory_1.md, algo_arrays_and_hashing_theory_2.md · generated by tools/build_lessons.py