DSA · Pattern

Arrays & Hashing

Use a hash map when you need to ask, "Have I seen this value?" or "How many times has it appeared?" Average lookup takes O(1) time.

Simple summary: Arrays keep values in order. Hash maps and sets add fast lookup, counting, and grouping, usually at the cost of O(n) extra space. Example: For Two Sum on [2, 7, 11, 15] with target 9, at 7 you need 2 — if 2 is already in the map, return both indices.

1. When to use hashing

Find a pair by looking for its complement (Two Sum)
Count how often values appear (anagrams and frequency problems)
Check membership quickly (Contains Duplicate)
Group items by a shared key (Group Anagrams)

2. Example — Two Sum

Given [2, 7, 11, 15] and target 9, return the indices of two values whose sum is 9.

seen = {} for i, num in enumerate(nums): need = target - num if need in seen: return [seen[need], i] seen[num] = i Walkthrough: i=0, num=2, need=7 → seen={2:0} i=1, num=7, need=2 → 2 in seen → return [0, 1]

We make one pass. Each lookup and insert takes O(1) average time, so the total is O(n) time and O(n) space.

3. Example — Contains duplicate

Return true if any value appears twice.

seen = set() for num in nums: if num in seen: return True seen.add(num) return False

Another option is to sort and scan in O(n log n) time. A hash set keeps the code simple and gives O(n) average time, but uses O(n) extra space.

4. Example — Valid anagram

Are "listen" and "silent" anagrams? Same letter counts.

from collections import Counter return Counter(s) == Counter(t) # Or one array of 26 counts for lowercase a-z

5. Array + hash together

Group anagrams: key = sorted string or letter count tuple.

groups = {} for word in words: key = tuple(sorted(word)) groups.setdefault(key, []).append(word) return list(groups.values())

6. One more worked example — first repeated value

For [5, 2, 4, 2, 5], return the first value that repeats while scanning from left to right.

seen = set() for num in nums: if num in seen: return num seen.add(num) return None Walkthrough on [5, 2, 4, 2, 5]: see 5 → seen={5} see 2 → seen={5,2} see 4 → seen={5,2,4} see 2 again → return 2

The set records earlier values. The algorithm takes O(n) average time and O(n) extra space.

7. Common mistakes

Forgetting that a hash map uses extra memory — mention it in interviews
Using index as key when you need value counts (and vice versa)
Not deciding what to return for empty input or no match

Quick revision

Hash map = fast lookup / count / complement.
Two Sum: store value → index; check target - num.
Duplicate: set membership.
Anagram: same character counts.
Typical complexity: O(n) time, O(n) space.