Arrays and hash maps: the interview patterns you must know

Many coding problems look different but reduce to a few patterns. The first and most useful is the hash map (also called dictionary, object or map). It stores key-value pairs and, on average, finds, adds and removes a key in O(1) time. A hash set stores only keys and answers "have I seen this?" in O(1).

Examples below use JavaScript-style code, but the ideas apply in any language.

Pattern 1: "have I seen this before?" (sets)

Problem: does an array contain a duplicate?

Brute force compares every pair: O(n²). With a set it is one pass:

function hasDuplicate(nums) {
  const seen = new Set();
  for (const n of nums) {
    if (seen.has(n)) return true;
    seen.add(n);
  }
  return false;
}
// Time O(n), space O(n)

This trades space for time, a very common move.

Pattern 2: complement lookup (Two Sum)

Problem: given numbers and a target, find two indexes whose values add up to the target.

Brute force is O(n²). For each number you only need to know whether target - number was seen earlier:

function twoSum(nums, target) {
  const indexOf = new Map();          // value -> index
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (indexOf.has(need)) return [indexOf.get(need), i];
    indexOf.set(nums[i], i);
  }
  return [];
}
// Time O(n), space O(n)

Check before you insert, so an element is not paired with itself.

Pattern 3: frequency counting

Problem: are two strings anagrams? Which element appears most often?

Count occurrences with a map:

function isAnagram(a, b) {
  if (a.length !== b.length) return false;
  const count = {};
  for (const ch of a) count[ch] = (count[ch] || 0) + 1;
  for (const ch of b) {
    if (!count[ch]) return false;
    count[ch]--;
  }
  return true;
}
// Time O(n), space O(k) where k is the alphabet size

For lowercase letters only, a fixed array of 26 counters is even simpler and gives O(1) space.

Pattern 4: grouping by a key

Problem: group words that are anagrams of each other.

Use a canonical key (for example the sorted letters) and push each word into the list for that key:

function groupAnagrams(words) {
  const groups = new Map();
  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()];
}

Whenever you need to group or deduplicate items, ask: what key makes equal things look the same?

Pattern 5: prefix sums

Problem: answer many "sum of elements from index i to j" queries quickly, or count subarrays with a given sum.

Precompute prefix[k] = sum of the first k elements. Then the sum from i to j is prefix[j + 1] - prefix[i] in O(1).

For "count subarrays whose sum equals K", keep a map of how many times each prefix sum has occurred:

function subarraySum(nums, k) {
  const seen = new Map([[0, 1]]);     // prefix sum -> count
  let sum = 0, count = 0;
  for (const n of nums) {
    sum += n;
    count += seen.get(sum - k) || 0;
    seen.set(sum, (seen.get(sum) || 0) + 1);
  }
  return count;
}
// Time O(n), space O(n)

This works with negative numbers too, where sliding window does not.

Pattern 6: in-place array tricks

Sometimes memory is limited, or the array can be reused as storage:

• Use the array itself as a marker (for example mark visited indices by negating values) when allowed.
• Swap or overwrite elements while scanning with a read and write pointer.

State clearly if you modify the input and whether that is acceptable.

How to recognise these problems

Think of a hash map when you see:

• "Find a pair/complement", "count", "most frequent", "first non-repeating".
• "Duplicates", "unique", "anagram", "group by".
• A brute force with a nested loop to search for something. A map turns that inner search into O(1).

Common mistakes

• Using an array search (includes, indexOf) inside a loop, which hides O(n²).
• Forgetting empty input or single-element cases.
• Using mutable objects or arrays as map keys by accident.
• Not clarifying whether values can be negative, repeated or very large.
• Ignoring hash collisions in the worst case. Average O(1) is usually accepted, but you can mention it.

Practice problems to try

Contains Duplicate, Valid Anagram, Two Sum, Group Anagrams, Top K Frequent Elements, Longest Consecutive Sequence, Subarray Sum Equals K, Product of Array Except Self.

Takeaway: when you need fast lookup, counting or grouping, reach for a hash map or set. Trade a little memory for a drop from O(n²) to O(n), and use prefix sums for range-sum questions.

---

Interview prep and DSA series, Part 1 (core patterns): 2 of 5. Previous: Big-O notation explained: time and space complexity for interviews.