Arrays & Hashing

MNEMONIC Have I seen your other half?

PATTERN What this family is really about

Arrays & Hashing problems all share one theme: trading memory for speed. The input is an unsorted (or unordered) array and a nested O(n²) brute force is obvious — but by storing information about elements we've already processed into a hash structure, we can answer queries in O(1) and finish in a single linear pass.

There are two dominant sub-patterns:

• Hash Set — "seen so far". Membership queries: have I encountered this value before? Gives O(1) duplicate detection, complement lookup, and start-of-run checks.
• Hash Map — frequency / complement map. Counting or keyed lookup: how many times did X appear? or what index did I last see X at? Powers anagram detection, top-k, and Two Sum.

Prefix sums are a close cousin: precompute cumulative totals so any range query is O(1), and pair them with a complement map to count subarrays.

KEY IDEA The complement trick — reframe "find a pair" as a lookup

This converts every pair-search into a single-pass set/map lookup. The same reframing works for subarrays: subarray sum = k becomes prefix[j] − prefix[i] = k, i.e. prefix[i] = prefix[j] − k — a hash map lookup on the prefix sum seen so far.

The key discipline: populate the map before or after checking the current element depending on whether you need to avoid self-matching (Two Sum) or allow zero-length subarrays (prefix sum base case map.set(0,1)).

RECIPE Step-by-step approach for any Arrays & Hashing problem

1. Identify what you need to remember— a value's existence, its count, or its index. That decides Set vs Map.
2. Decide what to key on — the raw value, a complement, a sorted signature (anagram grouping), or a prefix sum.
3. Single pass: for each element, query first, then insert (or vice versa if you need to include the current element).
4. Watch your base case: prefix sum maps always pre-insert 0 → 1 so empty-prefix subarrays are counted.
5. Return the count, the indices, the map itself, or a derived structure (bucket sort by frequency for top-k).

COST Complexity profile

The tradeoff is always O(n) extra space. In the rare case where you can't afford that space, check whether sorting first (O(n log n) time, O(1) extra) unlocks a two-pointer solution instead.

RUN IT Have I seen your other half?

TRIGGERS When you see ___ → reach for ___

Reach for a hash map or set when the problem is fundamentally about membership, counting, or pairing within an unsorted array, and a nested loop is the obvious-but-slow solution. Prefix sums enter when the problem mentions subarrays, ranges, or cumulative totals.

RED FLAGSWhen it's NOT this pattern

• The array is sorted and you need O(1) space. A sorted input often means two pointers will work — e.g. Two Sum II. Hashing buys nothing over the O(1) pointer approach when order gives you the monotonicity you need.
• You need a contiguous subarray with a dynamic size constraint.If the problem involves shrinking and growing a window (e.g. "minimum window substring"), that's a sliding window problem — hashing still plays a supporting role, but the outer logic is window expansion/contraction, not a flat single pass.
• Keys are arrays or objects. JS/TS maps key objects by reference, not value. Stringify composite keys (e.g. JSON.stringify(sorted) for anagram groups, or `${r},${c}` for coordinate pairs) before using them as map keys.
• Problem asks for in-place or O(1) space. Hash structures allocate O(n) space, which violates strict in-place constraints. Fall back to sorting or index-sign tricks.

TEMPLATE Hash Set — seen so far

When → Membership queries: have I seen this value before? Classic for duplicate detection, set intersection, and start-of-run checks (Longest Consecutive Sequence).

function hasDuplicate(nums: number[]): boolean {
  const seen = new Set<number>();
  for (const n of nums) {
    if (seen.has(n)) return true;   // already encountered → duplicate found
    seen.add(n);
  }
  return false;
}

TEMPLATE Frequency map / counter

When → Counting occurrences — anagram detection, top-k elements, or validating that two structures have matching character/element tallies.

function topKFrequent(nums: number[], k: number): number[] {
  // 1. Count occurrences — O(n)
  const freq = new Map<number, number>();
  for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);

  // 2. Bucket sort by frequency — O(n), avoids O(n log n) heap
  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
  for (const [val, cnt] of freq) buckets[cnt].push(val);

  // 3. Collect from highest-frequency bucket downward
  const result: number[] = [];
  for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
    result.push(...buckets[i]);
  }
  return result.slice(0, k);
}

TEMPLATE Prefix sum + complement map

When → Count or locate subarrays whose elements sum to a target. The prefix sum turns any range query into a subtraction; the map makes the complement lookup O(1).

function subarraySum(nums: number[], k: number): number {
  // prefix[i] = sum of nums[0..i-1]; prefix[0] = 0
  const prefixCount = new Map<number, number>([[0, 1]]);  // base case
  let count = 0, runningSum = 0;

  for (const n of nums) {
    runningSum += n;
    // If (runningSum - k) was a previous prefix sum, the gap between
    // that earlier index and now is a subarray that sums to k.
    count += prefixCount.get(runningSum - k) ?? 0;
    prefixCount.set(runningSum, (prefixCount.get(runningSum) ?? 0) + 1);
  }
  return count;
}

TEMPLATE Complement lookup (Two Sum / pair search)

When → Find a pair of indices whose values satisfy a relationship (sum, product, difference). Build the map as you go so you never match an element with itself.

function twoSum(nums: number[], target: number): [number, number] {
  const seen = new Map<number, number>();  // value → index
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) return [seen.get(complement)!, i];
    seen.set(nums[i], i);                  // record AFTER checking — avoids self-match
  }
  throw new Error('no solution');
}

PITFALL Keying objects or arrays by reference

In JavaScript/TypeScript, new Map() uses reference equality for object and array keys. Two arrays [1,2,3] and [1,2,3] are different keys even if they look identical. Always convert composite keys to a string or primitive — e.g. arr.sort().join(',') for anagram grouping — before inserting into a map.

PITFALL Forgetting the prefix-sum base case

The complement map for subarray-sum problems must be initialised with map.set(0, 1)before the loop. Without it, any subarray that starts at index 0 and sums to k is missed, because there is no "previous prefix" entry to match against.

PITFALL Using a plain object instead of Map for numeric keys

Plain JS objects coerce numeric keys to strings and iterate them in numeric-ascending order, which can cause subtle bugs. For frequency counting or prefix-sum maps where keys are numbers, use new Map<number, number>() — it preserves insertion order and handles negative keys correctly, unlike a plain object.

PITFALL Integer overflow in product problems

Product of Array Except Self and similar problems accumulate products across up to 10⁵ elements. JavaScript numbers are IEEE-754 doubles (safe integers up to 2⁵³), so overflow is rare in practice, but if a problem uses a typed language or large values, keep intermediate results modulo a prime or use BigInt. Always check the constraints before assuming products fit in a standard integer.

PROBLEMS