Goal: Check if any value appears at least twice.
Why Hash Set? Problem asks "have we seen this before?" Hash set provides O(1) lookup and insertion, perfect for membership queries. Alternative (sorting) is O(n log n).
Key Insight: Trading space for time. We memorize what we've seen to avoid re-scanning.
Goal: Check if strings `s` and `t` have exact same char counts.
Why Frequency Counting? Anagrams = same letters, different order. Order doesn't matter, only frequency. Sorting works but is O(n log n). Counting is O(n).
Key Insight: Fixed alphabet size (26) means O(1) space. Increment for first string, decrement for second. If all zeros, they're anagrams.
Unicode?
Use a generic HashMap `map[rune]int`.Goal: Find indices of two numbers adding to `target`.
Why Complement? Brute force is O(n²) checking all pairs. Instead of "what pairs sum to target?", ask "have I seen the complement (target - current)?"
Key Insight: For each number, we instantly know what value would complete the pair. Hash map gives O(1) lookup. Store as we go to avoid using same element twice.
Trap:
Don't use same element twice. Map check handles this (looks back).Goal: Group strings that are anagrams.
Why Character Count Key? Need a way to identify anagrams. Sorting each string works (O(n·k log k)) but counting is faster (O(n·k)). Same character frequencies = same key.
Key Insight: Use character frequency as the "signature" of an anagram group. All anagrams share the same signature. Group by this signature using a map.
In Go, arrays `[26]int` are comparable keys. In other langs, convert array to string "1#0#2...".
Goal: Find `k` most common numbers.
Why Bucket Sort? Need to rank by frequency. Heap is O(n log k). But frequency range is limited: 1 to n. This bounded range allows bucket sort in O(n).
Key Insight: Index = frequency, Value = numbers with that frequency. Walk backwards from highest frequency. Exploits the constraint that frequencies are bounded.
Goal: Serialize list of strings to one string.
Why Length Prefix? Simple delimiters (`,`, `|`) break if strings contain them. Escaping gets complex. Length prefix is unambiguous: tells you exactly how many chars to read.
Key Insight: Encode metadata (length) separate from data (string). Decoder knows where one string ends and next begins, regardless of content. Handles any character, even delimiter itself.
Stateless:
No global state needed, handles any char.Goal: Output[i] = product of all except nums[i]. No division.
Why Prefix/Suffix? Division trick (total product / nums[i]) fails with zeros. Instead, decompose: product except i = (product before i) × (product after i).
Key Insight: Build answer in two passes. First pass: accumulate products from left. Second pass: multiply by products from right. Clever use of output array avoids extra space.
Goal: Check duplicates in Row, Col, 3x3 Box.
Why Composite Keys? Need to track 27 constraints (9 rows, 9 cols, 9 boxes). Could use 27 sets, but encoding position+value into single key is cleaner.
Key Insight: Each cell participates in 3 constraints. Encode each as unique string: "r5:3" = "3 in row 5", "c2:3" = "3 in col 2", "b4:3" = "3 in box 4". One set tracks all.
Box Index: `(row / 3) * 3 + (col / 3)` maps (0..8, 0..8) to 0..8.
Goal: Length of longest seq (1, 2, 3, 4) in unsorted array.
Why Start-of-Sequence? Sorting finds sequences easily but is O(n log n). Hash set gives O(1) lookups. Key: only count from sequence starts to avoid redundant work.
Key Insight: If (n-1) exists, n is NOT a sequence start—skip it. Only when (n-1) missing, n begins a sequence. Walk forward counting n+1, n+2... Each element visited at most twice: once in outer loop, once in inner loop. Still O(n)!