Pair with a given sum in an unsorted array
Easy · Target 10 minutes · Arrays and hashing · Type asked at
Jane StreetCitadelTwo Sigma
Given an array nums in no particular order and an integer target,
return the indices of the two numbers that add up to target, smaller index first.
Exactly one such pair exists, and you may not use the same element twice.
Examples
| Input | Output | Why |
|---|---|---|
nums = [11, 2, 15, 7], target = 9 | [1, 3] | 2 + 7 = 9. |
nums = [3, 2, 4], target = 6 | [1, 2] | 2 + 4. Not [0, 0] — the 3 cannot be used twice. |
nums = [3, 3], target = 6 | [0, 1] | Two different elements that happen to be equal are fine. |
Constraints
- 2 ≤ n ≤ 10⁵
- −10⁹ ≤ nums[i] ≤ 10⁹
- Exactly one valid pair exists
Hints
Hint 1
Checking every pair works and is O(n²). Before optimising, say out loud what each inner loop is actually looking for.
Hint 2
For a value x, the inner loop is searching for one specific number: target − x. That is a lookup, and lookups are what hash maps are for.
Hint 3
Walk the array once. For each element, ask the map whether its partner has already gone past; only then add the element itself.
Dry run on [11,2,15,7],9
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5nums1102115273target9map{}
Empty map. Target 9. For each number, ask whether its partner has already gone past.
-
Step 2 / 5nums110i2115273need-2map{}
11 needs -2. Not in the map yet, so record 11 at index 0 and move on.
-
Step 3 / 5nums11021i15273need7map{11:0}
2 needs 7. Not in the map yet, so record 2 at index 1 and move on.
-
Step 4 / 5nums11021152i73need-6map{11:0, 2:1}
15 needs -6. Not in the map yet, so record 15 at index 2 and move on.
-
Step 5 / 5nums1102115273ineed2map{11:0, 2:1, 15:2}
7 needs 2, and 2 was seen at index 1. Answer [1, 3].
How to think about it
The brute force tries every pair. Look at what its inner loop is doing for a fixed
x: scanning the whole array for one particular value, target − x. It is a
search for a known key, repeated n times.
So remember what you have seen. Keep a map from value to index, and walk the array once. At each element, look up its complement. If the complement has already been passed, you have the pair — and because the complement was stored earlier, its index is automatically the smaller one.
The order of the two operations inside the loop is the whole problem. Look up first, then
insert. Insert first and on [3, 2, 4] with target 6 the 3 finds itself, and you
return [0, 0]. Looking up first also handles [3, 3] correctly: when the
second 3 arrives, the first is already in the map under a different index.
If the array had been sorted, two pointers would do this in O(1) extra space. The hash map buys the same speed without needing the order, at the price of O(n) memory.
Complexity. Time O(n) · Space O(n)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def pair_sum_unsorted(nums, target):
seen = {} # value -> index
for i, x in enumerate(nums):
if target - x in seen: # look up first...
return [seen[target - x], i]
seen[x] = i # ...then record, so x cannot pair with itself
return []#include <unordered_map>
#include <vector>
using namespace std;
vector<int> solve(vector<int> nums, long long target) {
unordered_map<long long, int> seen; // value -> index
for (int i = 0; i < (int)nums.size(); i++) {
auto it = seen.find(target - nums[i]); // look up first...
if (it != seen.end()) return {it->second, i};
seen[nums[i]] = i; // ...then record
}
return {};
}import java.util.*;
class Solution {
public int[] pairSumUnsorted(int[] nums, long target) {
Map<Long, Integer> seen = new HashMap<>(); // value -> index
for (int i = 0; i < nums.length; i++) {
Integer j = seen.get(target - nums[i]); // look up first...
if (j != null) return new int[]{j, i};
seen.put((long) nums[i], i); // ...then record
}
return new int[0];
}
}function pairSumUnsorted(nums, target) {
const seen = new Map(); // value -> index
for (let i = 0; i < nums.length; i++) {
const want = target - nums[i];
if (seen.has(want)) return [seen.get(want), i]; // look up first...
seen.set(nums[i], i); // ...then record
}
return [];
}use std::collections::HashMap;
fn solve(nums: &[i64], target: i64) -> Option<(usize, usize)> {
let mut seen: HashMap<i64, usize> = HashMap::new(); // value -> index
for (i, &x) in nums.iter().enumerate() {
if let Some(&j) = seen.get(&(target - x)) { // look up first...
return Some((j, i));
}
seen.insert(x, i); // ...then record
}
None
}import qualified Data.Map.Strict as M
solve :: [Int] -> Int -> Maybe (Int, Int)
solve xs target = go M.empty (zip [0 ..] xs)
where
go _ [] = Nothing
go seen ((i, x) : rest) =
case M.lookup (target - x) seen of -- look up first...
Just j -> Just (j, i)
Nothing -> go (M.insert x i seen) rest -- ...then recordWhere people lose marks
- Inserting before looking up, which lets an element pair with itself.
- Storing only the first index of each value and then being surprised by
[3, 3]. Looking up before inserting makes this a non-issue. - Sorting to use two pointers and then returning indices into the sorted copy. The question asks for positions in the original array.
- In C++ and Java,
target − xnear the integer limits overflows. Use a 64-bit type for the complement.
Variants to try
- The array is sorted. (Two pointers, O(1) space — see the two-pointer section.)
- Return every pair, not just one. (Store counts, and mind pairs of equal values.)
- Three numbers. (Sort, fix one, run two pointers on the rest: O(n²).)
Next problems
Longest run of consecutive integers
Sorting gives the answer in O(n log n). A set gives it in O(n), and the reason it is not O(n²) is the interesting part.
Open the problem → Medium15 minThe k most frequent values
A hash map does the counting in one pass. The interesting part is ordering what you counted, and saying precisely how ties break.
Open the problem → Medium20 minCount subarrays with a given sum
Negative numbers break the sliding window. Prefix sums in a hash map fix it, and the counting detail is where people slip.
Open the problem →Write a solution and run it against the real test table.
Keep going
Longest run of consecutive integers
Sorting gives the answer in O(n log n). A set gives it in O(n), and the reason it is not O(n²) is the interesting part.
Open the problem → Medium15 minThe k most frequent values
A hash map does the counting in one pass. The interesting part is ordering what you counted, and saying precisely how ties break.
Open the problem → Medium20 minCount subarrays with a given sum
Negative numbers break the sliding window. Prefix sums in a hash map fix it, and the counting detail is where people slip.
Open the problem → Arrays and hashingThe pattern behind it
Trade memory for time: a hash map answers "have I seen this?" in O(1), and most array problems reduce to asking it the right question.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.