DSA Patterns for Coding Interviews: The Techniques Behind Almost Every Problem

Part 4 of 16 · ~3 min

Hashing Patterns

Same 7-credit question as last chapter, minus one assumption. This time the elective list arrived unsorted — three departments each appended their own rows in whatever order they felt like:

const unsortedCredits = [4, 1, 5, 3, 2];   // same five values, no guaranteed order

Point twoElectivesSumTo at this and it quietly stops working — the whole trick behind moving left forward depended on the guarantee that doing so could only raise the sum, and that guarantee came entirely from sortedness. Sort first and the old function works again, but sorting costs O(n log n) up front. There's a cheaper route, and out of everything in this piece it might be the one pattern worth learning first: spend memory to buy speed. Remember what's already been seen in O(n) extra space, and an O(n²) pairwise check becomes a single O(n) pass with O(1) average lookups.

"Have I already seen this?"

function twoElectivesSumToUnsorted(credits, target) {
  const seen = new Map();                    // value -> index already scanned
  for (let i = 0; i < credits.length; i++) {
    const complement = target - credits[i];
    if (seen.has(complement)) {
      return [seen.get(complement), i];
    }
    seen.set(credits[i], i);                 // recorded AFTER the check — see below
  }
  return null;
}

For each elective, ask a map instead of the rest of the array: has the credit size that would complete this pair already gone by? That's an O(1) average lookup replacing a linear scan. Notice the order of operations — the map only gets credits[i] added to it after the complement check runs. Flip that order and an elective with no real partner could end up "pairing" with itself; doing the check first means a value only counts as its own match if it genuinely shows up twice in the list.

This is really the last chapter's problem with the floor pulled out from under it: same target, same O(n) payoff, but the source of the speed has flipped. Two pointers gets its speed from order the data already has. Hashing gets its speed from memory it builds as it goes. Telling them apart in the moment is mostly one question: is this sorted, or cheap to make sorted? If yes, two pointers, zero extra space. If not, and sorting isn't free, reach for the map instead.

Frequency counting

Two students want to know if they're registered for an identical set of courses this term, order aside — a natural "find a study partner" check:

function sameScheduleComposition(scheduleA, scheduleB) {
  if (scheduleA.length !== scheduleB.length) return false;
  const counts = new Map();
  for (const code of scheduleA) counts.set(code, (counts.get(code) || 0) + 1);
  for (const code of scheduleB) {
    if (!counts.has(code)) return false;
    counts.set(code, counts.get(code) - 1);
    if (counts.get(code) === 0) counts.delete(code);
  }
  return counts.size === 0;      // every count settled back to zero
}

Push the same value-to-count idea one step further and it becomes grouping: bucket sections by a computed key — a normalized, cross-listing-aware version of the course code — and every mutually-equivalent group falls into its own bucket automatically, no pairwise string comparisons involved.

One JavaScript trap worth knowing before it bites: a plain object turns every key into a string behind the scenes, so if two departments happen to use numeric internal section IDs, counts[1042] and counts["1042"] end up as the same property whether that was intended or not — and the failure is quiet, not loud. Map sidesteps this entirely: any value can be a key, insertion order survives, and .size is a real property instead of Object.keys(obj).length. Reach for Map by default the moment the keys are anything other than the simplest strings.

And a caveat worth carrying forward: that "average" in "O(1) average" isn't decorative. Enough keys colliding into the same bucket drags a lookup down toward O(n) in the worst case — it just takes a genuinely pathological key distribution to get there, and a real course catalog's codes are nowhere near that unlucky.

Practice this shape directly on Hash Table in Code Lab.