Two Sum

Two Sum is the question almost everyone gets first. So it feels simple, right? But the interviewer is not just asking for an answer. They want to see if you can take a slow solution and make it fast. That jump from slow to fast is the real test here.

🎯 The Problem

You get an array of numbers and one target number. You have to find two numbers in the array that add up to the target. Then you return their positions, not the numbers themselves.

Let us say the array is [2, 7, 11, 15] and the target is 9. Now 2 + 7 gives 9. So the answer is the positions 0 and 1. The partner of a number is called the complement. For 2, the complement is 7, because 2 + 7 reaches the target.

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]

Explanation: nums[0] + nums[1] = 2 + 7 = 9

You can assume there is exactly one pair that works. And you cannot use the same position twice.

🐢 The Brute Force Way

The first idea that comes to mind is simple. Pick one number. Then check it against every other number. If any pair adds up to the target, you found it.

So you walk through the array with one loop. For each number, you start a second loop that looks at all the numbers after it. You add the two and compare with the target.

This works. But see the problem? For every number you are scanning almost the whole array again. So the time grows fast. With a small array it feels fine. With a big array it becomes slow. We call this O(n²) time, because two nested loops over n items means about n times n steps.

In an interview you can mention this approach first. It shows you understand the problem. Then you say, “but we can do better,” and move on.

⚡ The Optimal Way: One Pass With a Hash Map

Here is the smarter idea. While you walk through the array once, keep a note of every number you have already seen. Store it in a hash map. A hash map is a structure that lets you store a key and a value, and look up the key almost instantly.

So what do we store? We store the number as the key and its position as the value.

Now think about what we actually need. For the current number, the partner we are looking for is target - current. That partner is the complement. So at each step, instead of scanning the rest of the array, we just ask the map one question: “have I already seen the complement?”

If yes, we are done. The map gives us the position of that earlier number, and the current position is the second one. If no, we add the current number to the map and move on.

The map lookup is almost instant. So we go through the array just one time. That makes it O(n). Much faster.

Steps to Solve

1. Create an empty hash map to store each number and its position.
2. Walk through the array one number at a time, with its index.
3. For the current number, calculate the complement, which is target - current.
4. Check the map for the complement. If it is there, return its stored position and the current position.
5. If it is not there, store the current number and its position in the map.
6. Keep going until you find the pair.

#include <stdio.h>
#include <string.h>

#define SIZE 1009  // a prime size for the hash table

int keys[SIZE];
int vals[SIZE];
int used[SIZE];

// turn a number into a table slot (handles negatives too)
int hashIndex(int key) {
    long h = ((long)key % SIZE + SIZE) % SIZE;
    while (used[h] && keys[h] != key) {
        h = (h + 1) % SIZE;  // linear probing
    }
    return (int)h;
}

void twoSum(int nums[], int n, int target, int result[]) {
    memset(used, 0, sizeof(used));
    for (int i = 0; i < n; i++) {
        int complement = target - nums[i];
        int slot = hashIndex(complement);
        if (used[slot]) {            // complement was seen before
            result[0] = vals[slot];
            result[1] = i;
            return;
        }
        int self = hashIndex(nums[i]);  // store current number
        keys[self] = nums[i];
        vals[self] = i;
        used[self] = 1;
    }
    result[0] = -1;  // no pair found
    result[1] = -1;
}

int main(void) {
    int nums[] = {2, 7, 11, 15};
    int target = 9;
    int result[2];
    twoSum(nums, 4, target, result);
    printf("[%d, %d]\n", result[0], result[1]);
    return 0;
}

[0, 1]

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;  // number -> its index
    for (int i = 0; i < (int)nums.size(); i++) {
        int complement = target - nums[i];
        if (seen.count(complement)) {      // found the partner
            return {seen[complement], i};
        }
        seen[nums[i]] = i;                 // remember this number
    }
    return {-1, -1};  // no pair found
}

int main() {
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    vector<int> result = twoSum(nums, target);
    cout << "[" << result[0] << ", " << result[1] << "]" << endl;
    return 0;
}

[0, 1]

import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();  // number -> index
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (seen.containsKey(complement)) {   // partner already seen
                return new int[] { seen.get(complement), i };
            }
            seen.put(nums[i], i);                 // remember this number
        }
        return new int[] { -1, -1 };  // no pair found
    }

    public static void main(String[] args) {
        int[] nums = { 2, 7, 11, 15 };
        int target = 9;
        int[] result = twoSum(nums, target);
        System.out.println("[" + result[0] + ", " + result[1] + "]");
    }
}

[0, 1]

def two_sum(nums, target):
    seen = {}  # number -> its index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:        # partner already seen
            return [seen[complement], i]
        seen[num] = i                 # remember this number
    return [-1, -1]                   # no pair found


nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))

[0, 1]

function twoSum(nums, target) {
  const seen = new Map(); // number -> its index
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) {        // partner already seen
      return [seen.get(complement), i];
    }
    seen.set(nums[i], i);              // remember this number
  }
  return [-1, -1]; // no pair found
}

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target));

[ 0, 1 ]

⏱️ Time and Space Complexity

The brute force uses two loops, so it is slow but needs no extra memory. The hash map uses one loop, so it is fast, but it needs extra memory to store the numbers it has seen. So you are trading a little memory to save a lot of time. That trade takes the time from O(n²) all the way down to O(n).

🧩 Key Takeaways

• ✅ The trick is to store numbers you have already seen, so you never scan the array twice.
• ✅ For each number, look for its complement, which is target - current.
• ✅ A hash map gives almost instant lookups, so the whole thing runs in O(n) time.
• ✅ You trade some extra memory for a big gain in speed.
• ✅ Talk through the brute force first, then the optimal one. The interviewer is grading your thinking.

🚀 What’s Next?

• Two Sum using HashMap
• Find the Missing Number