Two Sum Problem
In this page:
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
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;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 5 topics to unlock
0/5 topics done
Complete these topics first: