Problem overview
The method twoSum receives an array of integers, nums, and a target. It returns the indices of two different positions whose values add up to target, or [-1, -1] if there is no such pair. There is at most one solution, and the same index can't be used twice (two equal values at different indices are fine).
In the example, nums = [2, 7, 11, 15] and target = 9. The values at indices 0 and 1 are 2 and 7, which add up to 9, so the answer is [0, 1].
The statement also sets a budget of O(n log n) time and O(n) extra space. That rules out trying every pair, which takes O(n²), and points toward sorting.
Approach: sort, then binary search for the complement
If a value x belongs to the answer, its partner must be exactly target - x, the complement. Finding a given value in a sorted array takes O(log n) with binary search, so one search per element costs O(n log n) in total, the same as the sort.
Sorting causes one problem: it moves values away from their original positions, and the answer must use the original indices. The fix is to sort [value, originalIndex] pairs instead of bare values. Each value then carries its index with it.
For the pair at sorted position i, the search looks only at positions i + 1 and later. Every pair of positions has a left member, so the pair is found when the loop reaches that member. Starting at i + 1 also stops an element from being matched with itself.
Take nums = [3, 9, -2, 5] and target = 3. The sorted pairs are [-2, 2], [3, 0], [5, 3] and [9, 1]. At position 0 the value is -2, so the search looks for 5 in positions 1 to 3. It finds it at position 2, and the original indices stored in the two pairs are 2 and 3, so the answer is [2, 3].
A hash map would solve Two Sum in O(n) time. This lesson practises binary search, so it searches for each complement in the sorted array.
Step by step
- Create
sortedNums, typednumber[][]and empty. The annotation is needed because TypeScript can't tell what an empty array literal will hold. - Fill it with
[nums[i], i]pairs. The value goes first so that sorting by the first element sorts by value. - Sort with a comparator,
first[0] - second[0]. Without one,sortcompares elements as strings. - Loop over the sorted positions. Each pair is tried as the left member of the answer.
- Search for the complement.
this.binarySearch(sortedNums, i + 1, sortedNums.length - 1, target - sortedNums[i][0])looks in the positions to the right ofiand returns a sorted position, or -1. - On a hit, return the original indices,
sortedNums[i][1]andsortedNums[j][1], notiandj. - After the loop, return
[-1, -1]. The loop only finishes without returning when no pair matches. - Declare the helper above
twoSum. It takes the pairs, the inclusive rangefirsttolast, and thevalueto find. - Loop while the range is non-empty:
first <= last. - Take the middle as
first + Math.floor((last - first) / 2). - If the middle value equals
value, returnmiddle. - If it is smaller, discard the left half with
first = middle + 1. - Otherwise discard the right half with
last = middle - 1. - Return -1 once the range is empty.
The solution in TypeScript
class Solution {
binarySearch(sortedNums: number[][], first: number, last: number, value: number): number {
while (first <= last) {
let middle = first + Math.floor((last - first) / 2);
if (sortedNums[middle][0] == value) {
return middle;
} else if (sortedNums[middle][0] < value) {
first = middle + 1;
} else {
last = middle - 1;
}
}
return -1;
}
twoSum(nums: number[], target: number): number[] {
let sortedNums: number[][] = [];
for (let i = 0; i < nums.length; ++i) {
sortedNums.push([nums[i], i]);
}
sortedNums.sort((first, second) => first[0] - second[0]);
for (let i = 0; i < sortedNums.length; i++) {
let j = this.binarySearch(sortedNums, i + 1, sortedNums.length - 1, target - sortedNums[i][0]);
if (j != -1) {
return [sortedNums[i][1], sortedNums[j][1]];
}
}
return [-1, -1];
}
}
The TypeScript details worth a closer look:
- The comparator.
sortwith no comparator turns elements into strings and compares those.[10, 9, 1].sort()gives[1, 10, 9], and sorting the pairs without a comparator would order them by the text of the pair, so[10, 0]would come before[9, 1]. The comparator returns a negative number, zero or a positive number, and subtracting the values does exactly that. - Sorting changes the array in place.
sortedNumsis a separate array of pairs, so the caller'snumsstays untouched. - No integer overflow. A
numberis a double, sofirst + Math.floor((last - first) / 2)could be written as(first + last) / 2without risk here. Integers only lose precision beyond 2^53, far beyond any array index.Math.flooris still needed, because/can give a fraction such as 2.5. ==works here, but===is the usual habit. Both sides are numbers, so the two operators agree.- Types are erased.
number[][]documents the pairs and lets the compiler check them, but the compiled JavaScript contains no trace of it.
Complexity
Time: O(n log n). Building the pairs is O(n) and sorting is O(n log n). The loop makes up to n binary searches of O(log n) each, which is O(n log n) again.
Space: O(n). sortedNums holds one small array per element. The binary search uses a few variables.
Edge cases and common mistakes
- Fewer than two elements. For an empty array the loop never runs. For one element the search range
i + 1to0is empty. Both return[-1, -1]. - Equal values.
[3, 3]with target 6 gives[0, 1]. The two 3s are different positions, and the search for the second one starts at position 1. - Pairing an element with itself.
[3, 4]with target 6 must give[-1, -1]. Starting the search atiwould match the 3 with itself. - Returning sorted positions. The answer comes from the second element of each pair. Returning
iandjwould be wrong whenever sorting moved something. - Forgetting the comparator. The pairs end up in the wrong order and the search misses answers.
- Order of the result. The index of the smaller value comes first. For
[7, 2]and target 9, the function returns[1, 0]. - Using
first < last. A range with a single element would never be examined.
Testing
nums = [2, 7, 11, 15],target = 9gives[0, 1].nums = [3, 9, -2, 5],target = 3gives[2, 3].nums = [-3, 4, 3, 90],target = 0gives[0, 2].nums = [3, 4],target = 6gives[-1, -1].nums = [],target = 5gives[-1, -1].