Interview OS
Back to Coding Prep

Coding

Two Sum

Hash maps · Easy

Hash mapsEasy

Overview

Two Sum: given an array and a target, return the indices of the two numbers that add up to it. The naive double loop is O(n²); a hash map storing each value's index turns it into a single O(n) complement lookup.

How it works

Hash maps
InputStoreCheckOutputnums, targetarraySeen mapmapComplementO(1)Index pairO(n)
ClientDataServiceEdge

Step by step, with examples

  1. 1

    nums, target

    • Find two indices summing to target.
  2. 2

    Seen map

    • Map each value to its index as you scan.
  3. 3

    Complement

    • Look up target − num in the map.
  4. 4

    Index pair

    • Return the two indices.
    • Example: [0,1]

Problem

Given an array of integers and a target, return the indices of the two numbers that add up to the target.

Approach

  • Scan once, storing value → index
  • Before inserting, check if target − num was already seen

Solution

function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return [];
}

Complexity

Time O(n), Space O(n).

Where this content comes from

For full transparency, this content is curated and verified from these sources:

Curated company-tagged problem banksRecurring interview pattern librariesOppZen-authored drills & solutions