← Back to DSA Course | Chapter 7: Hashing | Lesson 4 of 5

Two Sum Problem

Two Sum is like looking for two candy bars whose prices add up to exactly the money you have. Remembering the prices you have seen helps you find the partner fast.

In this page:

  1. Problem Idea
  2. Brute Force
  3. Hashing Approach
  4. Example Thinking
  5. Complexity
Syntax
markup 
seen = {}
for i, num in enumerate(nums):
    complement = target - num
    if complement in seen:
        return [seen[complement], i]
    seen[num] = i

Problem Idea

Two Sum asks you to find two numbers in an array that add up to a given target and return their positions. It's one of the most common first interview questions because the naive solution is obvious but the optimal one requires a real insight about trading space for time.

Example: Problem Idea

#include <iostream>
using namespace std;
int main() {
	int nums[] = {2, 7, 11, 15};
	int target = 9;
	cout << "Find two numbers in the array summing to " << target;
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] nums = {2, 7, 11, 15};
		int target = 9;
		System.out.println("Find two numbers in the array summing to " + target);
	}
}
nums = [2, 7, 11, 15]
target = 9
print("Find two numbers in the array summing to", target)
#include <stdio.h>
int main() {
	int target = 9;
	printf("Find two numbers in the array summing to %d", target);
	return 0;
}

Brute Force

The brute-force approach checks every possible pair with two nested loops, comparing each element against every other element until a matching pair is found. It's easy to write correctly but becomes slow quickly as the array grows, since the number of pairs grows quadratically.

Example: Brute Force

#include <iostream>
using namespace std;
int main() {
	int nums[] = {2, 7, 11, 15};
	int target = 9;
	for (int i = 0; i < 4; i++)
		for (int j = i + 1; j < 4; j++)
			if (nums[i] + nums[j] == target) cout << i << " " << j;
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] nums = {2, 7, 11, 15};
		int target = 9;
		for (int i = 0; i < 4; i++)
			for (int j = i + 1; j < 4; j++)
				if (nums[i] + nums[j] == target) System.out.println(i + " " + j);
	}
}
nums = [2, 7, 11, 15]
target = 9
for i in range(4):
    for j in range(i + 1, 4):
        if nums[i] + nums[j] == target:
            print(i, j)
#include <stdio.h>
int main() {
	int nums[] = {2, 7, 11, 15};
	int target = 9;
	for (int i = 0; i < 4; i++)
		for (int j = i + 1; j < 4; j++)
			if (nums[i] + nums[j] == target) printf("%d %d", i, j);
	return 0;
}

Hashing Approach

Instead of comparing pairs directly, you can store each number you've already seen in a hash map as you scan the array once. This turns 'have I seen this value before' into a single O(1) lookup instead of rescanning the whole array.

Example: Hashing Approach

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
	int nums[] = {2, 7, 11, 15};
	int target = 9;
	unordered_map<int, int> seen;
	for (int i = 0; i < 4; i++) {
		if (seen.count(nums[i])) cout << seen[nums[i]] << " " << i;
		seen[target - nums[i]] = i;
	}
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] nums = {2, 7, 11, 15};
		int target = 9;
		Map<Integer, Integer> seen = new HashMap<>();
		for (int i = 0; i < 4; i++) {
			if (seen.containsKey(nums[i])) System.out.println(seen.get(nums[i]) + " " + i);
			seen.put(target - nums[i], i);
		}
	}
}
nums = [2, 7, 11, 15]
target = 9
seen = {}
for i, n in enumerate(nums):
    if n in seen:
        print(seen[n], i)
    seen[target - n] = i
#include <stdio.h>
int main() {
	int nums[] = {2, 7, 11, 15};
	int target = 9;
	int seenVal[10], seenIdx[10], count = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < count; j++) {
			if (seenVal[j] == nums[i]) printf("%d %d", seenIdx[j], i);
		}
		seenVal[count] = target - nums[i]; seenIdx[count] = i; count++;
	}
	return 0;
}

Example Thinking

For each new number, compute what its partner would need to be (target minus the current value) and check if that partner is already in the map. If it is, you've found your pair immediately; if not, add the current number to the map and keep scanning.

Example: Example Thinking

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
	int nums[] = {2, 7, 11, 15};
	int target = 9;
	unordered_map<int, int> seen;
	for (int i = 0; i < 4; i++) {
		int partner = target - nums[i];
		if (seen.count(partner)) { cout << "Found pair at " << seen[partner] << " and " << i; break; }
		seen[nums[i]] = i;
	}
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[] nums = {2, 7, 11, 15};
		int target = 9;
		Map<Integer, Integer> seen = new HashMap<>();
		for (int i = 0; i < 4; i++) {
			int partner = target - nums[i];
			if (seen.containsKey(partner)) { System.out.println("Found pair at " + seen.get(partner) + " and " + i); break; }
			seen.put(nums[i], i);
		}
	}
}
nums = [2, 7, 11, 15]
target = 9
seen = {}
for i, n in enumerate(nums):
    partner = target - n
    if partner in seen:
        print("Found pair at", seen[partner], "and", i)
        break
    seen[n] = i
#include <stdio.h>
int main() {
	int nums[] = {2, 7, 11, 15};
	int target = 9;
	int seenVal[10], seenIdx[10], count = 0;
	for (int i = 0; i < 4; i++) {
		int partner = target - nums[i];
		int found = 0;
		for (int j = 0; j < count; j++) if (seenVal[j] == partner) { printf("Found pair at %d and %d", seenIdx[j], i); found = 1; break; }
		if (found) break;
		seenVal[count] = nums[i]; seenIdx[count] = i; count++;
	}
	return 0;
}

Complexity

The brute-force pair check costs O(n²) time because every element is compared against every other. The hashing approach trades that for O(n) extra space to store seen values, bringing the typical running time down to O(n).

Example: Complexity

#include <iostream>
using namespace std;
int main() {
	int n = 1000;
	long bruteForceOps = (long)n * n;
	long hashingOps = n;
	cout << "Brute force: O(n^2) = " << bruteForceOps << " ops\n";
	cout << "Hashing: O(n) = " << hashingOps << " ops";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int n = 1000;
		long bruteForceOps = (long) n * n;
		long hashingOps = n;
		System.out.println("Brute force: O(n^2) = " + bruteForceOps + " ops");
		System.out.println("Hashing: O(n) = " + hashingOps + " ops");
	}
}
n = 1000
brute_force_ops = n * n
hashing_ops = n
print("Brute force: O(n^2) =", brute_force_ops, "ops")
print("Hashing: O(n) =", hashing_ops, "ops")
#include <stdio.h>
int main() {
	long n = 1000;
	long bruteForceOps = n * n;
	long hashingOps = n;
	printf("Brute force: O(n^2) = %ld ops\n", bruteForceOps);
	printf("Hashing: O(n) = %ld ops", hashingOps);
	return 0;
}
Related Topics

Prefix Sum · N-Queens Problem · Merge Two Sorted Lists · Two Pointer Technique

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
Common Mistakes
  1. Checking nums[i] + nums[i] == target and reusing the same element twice, when each index can only be used once.
  2. Inserting the current number into the map before checking for its complement, which can pair an element with itself.
  3. Using two nested loops as the final solution, which is O(n^2) where a hash map gives O(n).
🔒

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Collision Handling Next Lesson → Frequency Counting

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.