Approach Summary
Store complement (target - num) in map as you iterate. If current num is already in map, you found the pair.
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Brute Force (Nested Loops) | O(n²) | O(1) | Examine every distinct pair of indices (i, j) and check if their sum matches target. |
| 2 Approach 2: Hash Map Lookup (Optimal) | O(n) | O(n) | Trade space for time by storing visited elements in a hash map for instant O(1) complement lookups. |
Approach 1: Brute Force (Nested Loops)
Loop through the array with pointer i from 0 to n - 1, and an inner pointer j from i + 1 to n - 1. For each combination, compute nums[i] + nums[j]. If the sum equals the target, return [i, j]. While intuitive and requiring zero auxiliary memory, this quadratic approach requires ~n²/2 comparisons, which triggers Time Limit Exceeded (TLE) when n = 10⁴ or greater.
Approach 1: Brute Force (Nested Loops) Implementation
Approach 1: Brute Force (Nested Loops)
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[]{};
}
}class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {};
}
};def two_sum(nums: list[int], target: int) -> list[int]:
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []function twoSum(nums, target) {
const n = nums.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}Approach 2: Hash Map Lookup (Optimal)
Instead of repeatedly scanning the array to find what number pairs with nums[i], maintain a hash table of previously visited numbers. For each element, check if target - nums[i] exists in the map. If it does, return the stored index along with the current index i. If not, record nums[i] -> i in the hash map. This resolves the problem in a single pass of linear time.
Approach 2: Hash Map Lookup (Optimal) Implementation
Approach 2: Hash Map Lookup (Optimal)
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
int result[] = new int[2];
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
result[0] = map.get(target - nums[i]);
result[1] = i;
return result;
} else {
map.put(nums[i], i);
}
}
return result;
}
}class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> m;
vector<int> ans;
int length = nums.size();
for (int i = 0; i < length; i++) {
int key = target - nums[i];
if (m.find(key) != m.end()) {
ans.push_back(m[key]);
ans.push_back(i);
return ans;
} else {
m[nums[i]] = i;
}
}
return ans;
}
};def two_sum(nums: list[int], target: int) -> list[int]:
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []function twoSum(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (map.has(complement)) {
return [map.get(complement), i];
}
map.set(nums[i], i);
}
return [];
}Edge Cases to Watch
- Negative numbers and zeros in nums or target
- Pairs located at the very beginning and end of the array
- Duplicate values where target is exactly twice the value (handled because check precedes insertion)
- Large arrays where quadratic nested loops would exceed the time limit
Master the Hash Map / Set Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Hash Map / Set pattern.
How to Recognize This Pattern
- Find pair summing to target
- Return indices
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)