Two Sum and Its Variants — Hash Map Pattern

You're 20 minutes into a Google interview. The question is Two Sum. You know you've seen this before — but the interviewer isn't looking for the answer, they're looking for how you think. Do you reach for the nested loop, or do you immediately see the hash map opportunity? That distinction is what separates a "hire" from a "no hire" for this problem.

This post walks through the hash map lookup pattern, how to recognize it, and three variants that show up in interviews. By the end, you'll see why this single mental model — trade space for time by storing what you've seen — appears in dozens of interview problems.

The Pattern: Store What You've Seen

The hash map pattern in array problems works like this: instead of asking "does anything in the array complement what I'm looking at?" via a nested loop, you flip the question — "have I already seen what I need?" You store elements as you go and check the map in O(1).

The signal to reach for this pattern:

• You need to find a pair (or group) of elements that satisfy some condition
• A brute force would require comparing every element to every other element
• The complement of what you need can be computed from the current element

Problem 1: Two Sum (LeetCode #1)

The setup: Given an array of integers nums and a target integer, return indices of the two numbers that add up to the target. Assume exactly one solution exists.

Brute Force First

Most people reach for the nested loop here — that's natural, it's the literal translation of "check every pair":

// Input: nums = [2, 7, 11, 15], target = 9
// Output: [0, 1]
 
const twoSumBrute = (nums, target) => {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return [];
};
// Time: O(n²) | Space: O(1)

This works, but you'd never pass an interview with it. An O(n²) solution on an array problem almost always signals a missed hash map or sorting opportunity.

Optimized: One-Pass Hash Map

// Input: nums = [2, 7, 11, 15], target = 9
// Output: [0, 1]
 
const twoSum = (nums, target) => {
  const seen = new Map(); // value → index
 
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
 
    // If we've seen the complement before, we have our pair
    if (seen.has(complement)) {
      return [seen.get(complement), i];
    }
 
    // Otherwise, record this number for future lookups
    seen.set(nums[i], i);
  }
 
  return [];
};
// Time: O(n) | Space: O(n)

Walk through it out loud in an interview: "I compute the complement at each step and check if I've already seen it. If yes — done. If no — store the current value and move on." That's the full explanation. Clean, clear, O(n).

Problem 2: Two Sum II — Input Array Is Sorted (LeetCode #167)

The setup: Same goal, but the input is already sorted in non-decreasing order. Return 1-indexed positions.

When the interviewer tells you the array is sorted, they're giving you a hint: the two-pointer approach is the intended solution. Hash maps still work but waste the sorted property.

// Input: numbers = [2, 7, 11, 15], target = 9
// Output: [1, 2]  (1-indexed)
 
const twoSumSorted = (numbers, target) => {
  let left = 0;
  let right = numbers.length - 1;
 
  while (left < right) {
    const currentSum = numbers[left] + numbers[right];
 
    if (currentSum === target) {
      // Convert to 1-indexed
      return [left + 1, right + 1];
    } else if (currentSum < target) {
      // Sum is too small — move left pointer right to increase sum
      left++;
    } else {
      // Sum is too large — move right pointer left to decrease sum
      right--;
    }
  }
 
  return [];
};
// Time: O(n) | Space: O(1)

This is important for interviews: recognize when a constraint (like sorted order) changes the optimal approach. Using a hash map here would get you O(n) time but O(n) space — the two-pointer solution is O(n) time and O(1) space, which is strictly better.

Problem 3: 3Sum (LeetCode #15)

The setup: Find all unique triplets in the array that sum to zero.

This is where the pattern gets tested. You can't do better than O(n²) here, but the trick is combining sorting + two pointers to avoid duplicates cleanly.

// Input: nums = [-1, 0, 1, 2, -1, -4]
// Output: [[-1, -1, 2], [-1, 0, 1]]
 
const threeSum = (nums) => {
  nums.sort((a, b) => a - b); // Sort to enable two-pointer + dedup
  const result = [];
 
  for (let i = 0; i < nums.length - 2; i++) {
    // Skip duplicates for the fixed element
    if (i > 0 && nums[i] === nums[i - 1]) continue;
 
    let left = i + 1;
    let right = nums.length - 1;
 
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
 
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
 
        // Skip duplicates for both pointers after finding a valid triplet
        while (left < right && nums[left] === nums[left + 1]) left++;
        while (left < right && nums[right] === nums[right - 1]) right--;
 
        left++;
        right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }
 
  return result;
};
// Time: O(n²) | Space: O(1) excluding output

The duplicate-skipping logic is what trips people up. When you find a valid triplet, you need to advance both pointers past any duplicate values. The while loops after result.push handle this.

Complexity Cheat Sheet

Interview Tips

1. State the brute force, then immediately improve it. Say "the naive approach is O(n²) with a nested loop — but I can trade O(n) space for O(n) time by using a hash map." This shows you understand the tradeoff and aren't just pattern-matching.

2. When you see sorted input, reconsider the hash map. Sorted arrays almost always have a two-pointer solution that's O(1) space. Interviewers give you sorted input for a reason.

3. For 3Sum and beyond, fix one element and reduce. Any k-sum problem (k ≥ 3) can be solved by fixing the outermost element and recursively solving (k-1)-sum on the rest. 3Sum reduces to 2Sum, 4Sum reduces to 3Sum, etc. Knowing this pattern handles a whole family of follow-up questions.