Two Sum
Description
You are given an array of integers and a target value. Your task is to find two distinct elements from the array whose sum equals the target value. Once you find such a pair, return the indices (positions) of these two numbers in the array.
A few important points to note:
- The array is guaranteed to have exactly one valid solution, meaning there will always be one pair that adds up to the target.
- You cannot use the same element twice. For example, if the target is 6 and the array contains [3, 2, 4], you cannot use index 0 (value 3) twice to get 3 + 3 = 6.
- The order in which you return the indices does not matter. Both [0, 1] and [1, 0] would be accepted as valid answers if both refer to a correct pair.
Examples
Example 1
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: We need to find two numbers that add up to 9. Looking at the array:
- nums[0] = 2
- nums[1] = 7
- 2 + 7 = 9, which equals our target
Therefore, we return the indices [0, 1] because the elements at these positions sum to the target value.
Example 2
Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
Explanation: We need to find two numbers that add up to 6. Let's check:
- nums[0] = 3, nums[1] = 2 → 3 + 2 = 5 (not 6)
- nums[0] = 3, nums[2] = 4 → 3 + 4 = 7 (not 6)
- nums[1] = 2, nums[2] = 4 → 2 + 4 = 6 ✓
The pair at indices [1, 2] gives us the sum of 6, so we return [1, 2].
Example 3
Input: nums = [3, 3], target = 6
Output: [0, 1]
Explanation: This example shows that the array can contain duplicate values. We have:
- nums[0] = 3
- nums[1] = 3
- 3 + 3 = 6, which equals our target
Even though both elements have the same value, they are at different indices (0 and 1), so this is a valid pair. We return [0, 1].
Constraints
- 2 ≤ nums.length ≤ 10^4
- -10^9 ≤ nums[i] ≤ 10^9
- -10^9 ≤ target ≤ 10^9
- Only one valid answer exists (the problem guarantees exactly one solution)
Editorial
Brute Force
Intuition
The most straightforward way to solve this problem is to check every possible pair of elements in the array. Imagine you're holding a list of numbers and you want to find two that add up to a specific value. The natural approach would be to:
- Pick the first number
- Check it against every other number to see if they sum to the target
- If no match is found, move to the second number and repeat
- Continue until you find a matching pair
This is exactly what the brute force approach does. We systematically examine all possible combinations of two different elements. For each element at position i, we look at all elements at positions j (where j > i) and check if their sum equals the target.
Step-by-Step Explanation
Let's trace through with nums = [3, 2, 4], target = 6
Step 1: Start with i = 0 (value = 3). Set j = 1 (value = 2). Compute sum = 3 + 2 = 5. Since 5 ≠ 6, no match.
Step 2: Keep i = 0, move j = 2 (value = 4). Compute sum = 3 + 4 = 7. Since 7 ≠ 6, no match. All j values exhausted for i = 0.
Step 3: Move i = 1 (value = 2). Set j = 2 (value = 4). Compute sum = 2 + 4 = 6. Since 6 = 6, we found a match!
Result: Return [1, 2]
Brute Force — Check Every Pair — Watch how two nested loops systematically check every pair of elements, computing their sum and comparing against the target.
Algorithm
- Use an outer loop with index i from 0 to n-2 (second to last element)
- For each i, use an inner loop with index j from i+1 to n-1 (last element)
- For each pair (i, j), calculate the sum: nums[i] + nums[j]
- If the sum equals the target, return [i, j]
- If no pair is found after checking all combinations, return an empty result (though the problem guarantees a solution exists)
Code
#include <vector>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
// Check every possible pair
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// If this pair sums to target, return their indices
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
// No solution found (shouldn't happen per problem constraints)
return {};
}
};class Solution:
def twoSum(self, nums: list[int], target: int) -> list[int]:
n = len(nums)
# Check every possible pair
for i in range(n - 1):
for j in range(i + 1, n):
# If this pair sums to target, return their indices
if nums[i] + nums[j] == target:
return [i, j]
# No solution found (shouldn't happen per problem constraints)
return []class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
// Check every possible pair
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// If this pair sums to target, return their indices
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
// No solution found (shouldn't happen per problem constraints)
return new int[]{};
}
}Complexity Analysis
Time Complexity: O(n²)
We have two nested loops. The outer loop runs n-1 times, and for each iteration of the outer loop, the inner loop runs progressively fewer times (n-1, n-2, n-3, ..., 1). The total number of pairs checked is:
(n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2
In Big-O notation, we drop constants, so this simplifies to O(n²).
Space Complexity: O(1)
We only use a fixed number of variables (i, j, n) regardless of the input size. The space used does not grow with the size of the input array, making this a constant space solution.
Why This Approach Is Not Efficient
The brute force approach has O(n²) time complexity, which becomes problematic for larger inputs. Given the constraint that n can be up to 10^4 (10,000 elements), the brute force approach would need to check approximately:
10,000 × 10,000 / 2 = 50,000,000 (50 million) pairs
While this might still pass within typical time limits for this specific problem, it's far from optimal. The key inefficiency is that for every element, we're scanning through the remaining array to find its complement (target - current element).
The question we should ask ourselves: Can we find the complement of each element faster than scanning the entire array?
The answer is yes! Instead of repeatedly searching through the array, we can use data structures that provide faster lookup times. This leads us to consider:
- Sorting + Two Pointers — O(n log n) approach
- Hash Map — O(n) approach
Let's explore the sorting approach first as an intermediate optimization.
Better Approach - Sorting with Two Pointers
Intuition
If the array were sorted, we could use a clever technique called "two pointers" to find the pair more efficiently. Here's the key insight:
In a sorted array, if we place one pointer at the beginning (smallest element) and another at the end (largest element), we can intelligently move them based on the sum:
- If the sum is too small, we need a larger number → move the left pointer right
- If the sum is too large, we need a smaller number → move the right pointer left
- If the sum equals the target, we found our pair!
However, there's a catch for this specific problem: we need to return the original indices, not the indices in the sorted array. So we need to store the original indices before sorting.
This approach trades some complexity for speed — we sort once (O(n log n)), then find the pair in linear time (O(n)), resulting in O(n log n) overall.
Step-by-Step Explanation
Let's trace through with nums = [2, 7, 11, 15], target = 9
Step 1: Create pairs of (value, original_index) and sort by value. The array is already sorted: [(2, 0), (7, 1), (11, 2), (15, 3)].
Step 2: Initialize two pointers — left = 0 (value 2), right = 3 (value 15). Compute sum = 2 + 15 = 17.
Step 3: Since 17 > 9, the sum is too large. Move right pointer left to index 2 (value 11). Compute sum = 2 + 11 = 13.
Step 4: Since 13 > 9, still too large. Move right pointer left to index 1 (value 7). Compute sum = 2 + 7 = 9.
Step 5: Since 9 == 9, we found the pair! The original indices are 0 and 1.
Result: Return [0, 1]
Two Pointers on Sorted Array — Converging Search — Watch how two pointers start at opposite ends of a sorted array and converge toward each other, narrowing the search space based on whether the current sum is too large or too small.
Algorithm
- Create a list of pairs where each pair contains (element value, original index)
- Sort this list by element values
- Initialize two pointers: left at index 0, right at index n-1
- While left < right:
- Calculate sum = sorted[left].value + sorted[right].value
- If sum == target, return the original indices [sorted[left].index, sorted[right].index]
- If sum < target, increment left (we need a larger sum)
- If sum > target, decrement right (we need a smaller sum)
- Return empty result if no pair found
Code
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
// Create pairs of (value, original_index)
vector<pair<int, int>> numWithIndex;
for (int i = 0; i < n; i++) {
numWithIndex.push_back({nums[i], i});
}
// Sort by value
sort(numWithIndex.begin(), numWithIndex.end());
// Two pointer approach
int left = 0;
int right = n - 1;
while (left < right) {
int sum = numWithIndex[left].first + numWithIndex[right].first;
if (sum == target) {
return {numWithIndex[left].second, numWithIndex[right].second};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return {};
}
};class Solution:
def twoSum(self, nums: list[int], target: int) -> list[int]:
# Create pairs of (value, original_index)
num_with_index = [(num, i) for i, num in enumerate(nums)]
# Sort by value
num_with_index.sort()
# Two pointer approach
left = 0
right = len(nums) - 1
while left < right:
current_sum = num_with_index[left][0] + num_with_index[right][0]
if current_sum == target:
return [num_with_index[left][1], num_with_index[right][1]]
elif current_sum < target:
left += 1
else:
right -= 1
return []import java.util.Arrays;
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
// Create array of {value, original_index}
int[][] numWithIndex = new int[n][2];
for (int i = 0; i < n; i++) {
numWithIndex[i][0] = nums[i];
numWithIndex[i][1] = i;
}
// Sort by value
Arrays.sort(numWithIndex, (a, b) -> Integer.compare(a[0], b[0]));
// Two pointer approach
int left = 0;
int right = n - 1;
while (left < right) {
int sum = numWithIndex[left][0] + numWithIndex[right][0];
if (sum == target) {
return new int[]{numWithIndex[left][1], numWithIndex[right][1]};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return new int[]{};
}
}Complexity Analysis
Time Complexity: O(n log n)
The time complexity is dominated by the sorting step:
- Creating pairs: O(n) — we iterate through the array once
- Sorting: O(n log n) — standard comparison-based sorting
- Two-pointer traversal: O(n) — each pointer moves at most n times in total
Total: O(n) + O(n log n) + O(n) = O(n log n)
Space Complexity: O(n)
We create a new array of n pairs to store the values along with their original indices. This additional storage is necessary because sorting would otherwise lose the original index information.
Why This Approach Is Not Efficient
While the sorting approach improves upon the brute force O(n²) complexity, achieving O(n log n), it still has room for optimization:
-
Unnecessary Work: Sorting rearranges ALL elements in the array, but we only need to find ONE specific pair. Sorting does more work than necessary for this particular problem.
-
Extra Space: We need O(n) extra space to store the original indices, which could be avoided.
-
Can We Do Better? The bottleneck in the brute force was searching for the complement of each element. With sorting, we improved the search but added the overhead of sorting itself.
Key Insight: What if we could look up the complement in O(1) time instead of O(log n) or O(n)?
This is exactly what a hash map (dictionary) provides! By using a hash map, we can:
- Look up any value in O(1) average time
- Store values as we iterate through the array
- Achieve O(n) overall time complexity
This leads us to the optimal solution.
Optimal Approach - Hash Map
Intuition
The key insight for the optimal solution comes from rethinking the problem: instead of asking "which two numbers sum to target?", we can ask for each number: "have I already seen the number that would complete this pair?"
Here's the elegant approach:
As we iterate through the array, for each element with value num, we calculate its "complement" — the value we need to reach the target: complement = target - num.
Now, instead of searching through the array for this complement (which takes O(n) time), we use a hash map that gives us O(1) lookup time. The hash map stores each number we've seen along with its index.
The beauty of this approach is that we can do everything in a single pass:
- Check if the complement exists in our hash map
- If yes, we found our pair!
- If no, add the current number to the hash map and continue
This transforms an O(n) search operation into an O(1) lookup, reducing overall complexity from O(n²) to O(n).
Step-by-Step Explanation
Let's trace through with nums = [3, 2, 4], target = 6
Step 1: Initialize an empty hash map. Process nums[0] = 3. Complement = 6 - 3 = 3. Is 3 in the map? No. Add 3 → index 0 to the map.
Step 2: Process nums[1] = 2. Complement = 6 - 2 = 4. Is 4 in the map? No. Add 2 → index 1 to the map.
Step 3: Process nums[2] = 4. Complement = 6 - 4 = 2. Is 2 in the map? Yes, at index 1! We found a pair: indices [1, 2].
Result: Return [1, 2]
Hash Map One-Pass — Build and Lookup Simultaneously — Watch how we build a hash map while scanning the array. For each element, we check if its complement already exists in the map. If found, we immediately return the answer.
Algorithm
- Create an empty hash map to store numbers and their indices
- Iterate through the array with index i:
- Calculate complement = target - nums[i]
- Check if complement exists in the hash map
- If yes, return [hash_map[complement], i]
- If no, add nums[i] to hash map with its index: hash_map[nums[i]] = i
- Return empty result if no pair found (shouldn't happen per problem constraints)
Code
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// Hash map to store value -> index mapping
unordered_map<int, int> numToIndex;
for (int i = 0; i < nums.size(); i++) {
// Calculate the complement we need
int complement = target - nums[i];
// Check if complement exists in our hash map
if (numToIndex.find(complement) != numToIndex.end()) {
// Found the pair! Return both indices
return {numToIndex[complement], i};
}
// Add current number to hash map
numToIndex[nums[i]] = i;
}
// No solution found (shouldn't happen per problem constraints)
return {};
}
};class Solution:
def twoSum(self, nums: list[int], target: int) -> list[int]:
# Dictionary to store value -> index mapping
num_to_index = {}
for i, num in enumerate(nums):
# Calculate the complement we need
complement = target - num
# Check if complement exists in our dictionary
if complement in num_to_index:
# Found the pair! Return both indices
return [num_to_index[complement], i]
# Add current number to dictionary
num_to_index[num] = i
# No solution found (shouldn't happen per problem constraints)
return []import java.util.HashMap;
import java.util.Map;
class Solution {
public int[] twoSum(int[] nums, int target) {
// Hash map to store value -> index mapping
Map<Integer, Integer> numToIndex = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
// Calculate the complement we need
int complement = target - nums[i];
// Check if complement exists in our hash map
if (numToIndex.containsKey(complement)) {
// Found the pair! Return both indices
return new int[]{numToIndex.get(complement), i};
}
// Add current number to hash map
numToIndex.put(nums[i], i);
}
// No solution found (shouldn't happen per problem constraints)
return new int[]{};
}
}Complexity Analysis
Time Complexity: O(n)
We iterate through the array exactly once. For each element, we perform:
- One hash map lookup: O(1) average case
- One hash map insertion: O(1) average case
Since we do O(1) work for each of the n elements, the total time complexity is O(n).
Note: In the worst case (many hash collisions), hash map operations could degrade to O(n), making the worst-case complexity O(n²). However, with a good hash function, the average case is O(n), which is what we typically consider.
Space Complexity: O(n)
In the worst case, we might need to store almost all n elements in the hash map before finding the pair (e.g., if the pair consists of the last two elements). Therefore, the space complexity is O(n).
Why This Is Optimal:
We must examine each element at least once to solve this problem (we can't know if an element is part of the solution without looking at it). This gives us a lower bound of Ω(n) for time complexity. Since our solution achieves O(n), it is optimal in terms of time complexity.
The space-time tradeoff here is worthwhile: we use O(n) extra space to reduce time from O(n²) to O(n).