LESSON 230 OF 348 · TWO POINTERS

Two Sum in TypeScript: O(n log n) with Sorting and Two Pointers

Practice O(n log n) + O(n) Read the full explanation

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input will have at most one solution, and you may not use the same index twice.

In case no solution exists, return [-1, -1]

Example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9

Note:

Your algorithm should run in O(n log n) time and use O(n) extra space.

STEP 1 OF 10

Guided

Ctrl + Enter to check

TYPESCRIPT · TWO POINTERS

Two Sum in TypeScript, explained

Problem overview

The method twoSum receives an array of numbers, nums, and a target. It returns the indices of two different positions whose values add up to target, or [-1, -1] when no such pair exists. There is at most one solution, and the same index can't be used twice, although 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, and 2 + 7 = 9, so the answer is [0, 1].

The statement also sets a budget: O(n log n) time and O(n) extra space. Checking every pair of indices costs O(n²), which is too slow. Sorting, followed by a single linear sweep, fits the budget.

Approach: sort, then squeeze from both ends

Once the values are in ascending order, a pair that sums to the target can be found with two pointers. One pointer starts at the smallest value, the other at the largest. Look at their sum:

If it equals the target, the pair is found.
If it is too small, the left pointer's value can't be part of any answer with the current right value or anything smaller, so move the left pointer one step right to get a larger value.
If it is too large, move the right pointer one step left to get a smaller value.

Every step discards at least one value that can no longer be in the answer, so the sweep takes O(n) steps. The sort dominates, which gives O(n log n) in total.

There is one catch. Sorting moves values away from their original positions, but the answer must contain the original indices. The fix is to sort [value, index] pairs instead of bare values. Each value then carries its index with it, wherever the sort puts it.

Here is the idea on nums = [3, 9, -2, 5] with target = 3. The sorted pairs are [[-2, 2], [3, 0], [5, 3], [9, 1]]. The pointers start at -2 and 9: the sum is 7, which is too large, so the right pointer moves to 5. Now -2 + 5 = 3, which is the target, so the method returns the stored indices, [2, 3].

Two Sum has other solutions too. A hash map reaches O(n) time, and a binary search for each complement also works. This lesson practises the two-pointer technique.

Step by step

Create the array of pairs. It has one slot per element, and each slot will hold a [number, number] tuple: the value and its original index.
Fill it. For every position i, store [nums[i], i].
Sort by value with a comparator that returns first[0] - second[0]. A negative result places first before second. The comparator is essential, as the next section explains.
Place the pointers at both ends of the sorted array: first at 0 and last at the final position.
Loop while first < last. When the pointers meet, every pair has been ruled out, and using the same element twice is not allowed anyway.
Add the two values, which sit at index 0 of each pair.
On a match, return the original indices, which sit at index 1 of each pair, not the sorted positions.
If the sum is too small, do first++. The values are ascending, so this can only increase the sum.
Otherwise do last--. This can only decrease the sum.
After the loop, return [-1, -1]. The loop ends without returning only when no pair adds up to the target.

The solution in TypeScript

class Solution {
    twoSum(nums: number[], target: number): number[] {
        let sortedNums: [number, number][] = new Array(nums.length);
        for (let i = 0; i < nums.length; ++i) {
            sortedNums[i] = [nums[i], i];
        }
        sortedNums.sort((first, second) => first[0] - second[0]);

        let first = 0, last = sortedNums.length - 1;
        while (first < last) {
            let sum = sortedNums[first][0] + sortedNums[last][0];
            if (sum === target) {
                return [sortedNums[first][1], sortedNums[last][1]];
            } else if (sum < target) {
                first++;
            } else {
                last--;
            }
        }
        return [-1, -1];
    }
}

The TypeScript details worth a closer look:

Tuple types. [number, number][] is an array of two-element arrays. The annotation lets the compiler check that sortedNums[i][0] and sortedNums[i][1] are numbers. At run time these are ordinary arrays, because types are erased when TypeScript compiles to JavaScript.
The comparator is required. Without one, sort() converts elements to strings and compares those. [10, 9, 1].sort() gives [1, 10, 9], and sorting the pairs without a comparator also compares their text, so [10, 0] would land before [9, 1]. The comparator first[0] - second[0] compares the numeric values.
Subtraction in a comparator. It is safe here because the values are ordinary numbers. A number is a double, so there is no integer overflow, and a comparator only needs the sign of the difference.
sort works in place. It rearranges sortedNums, not nums, so the caller's array stays as it was.
new Array(nums.length) makes an array of that length with empty slots. The loop fills every slot before the sort runs, so nothing empty is ever sorted.
=== compares the sum with the target without any type conversion.
Naming. The variables first and last are pointers (numbers) in the method body. The comparator's parameters are also called first and second, but they live only inside the arrow function and refer to pairs.

Complexity

Time: O(n log n). Building the pairs is O(n), sorting is O(n log n), and the sweep moves a pointer on every iteration, so it runs at most n - 1 times.

Space: O(n). The array of pairs holds one tuple per element. The pointers and the sum use constant space.

Edge cases and common mistakes

Fewer than two elements. An empty array gives last = -1, and one element gives first = last = 0. In both cases first < last is false from the start, so the method returns [-1, -1].
Equal values. [3, 3] with target 6 returns [0, 1]: the two 3s are at different indices, so they form a valid pair.
The same element twice. [3, 4] with target 6 returns [-1, -1]. The pointers never sit on the same position, so 3 is never paired with itself.
Returning sorted positions. first and last are positions in the sorted array. The answer comes from the second element of each pair.
Index order. The index of the smaller value comes first. For [7, 2] with target 9, the method returns [1, 0].
A missing comparator. Default string ordering breaks the sorted-order assumption, and the pointers then discard values that could have been in the answer.
Using <= in the loop. The pointers would be allowed to meet, and one element could pair with itself.

Testing

nums = [2, 7, 11, 15], target = 9 gives [0, 1].
nums = [3, 9, -2, 5], target = 3 gives [2, 3].
nums = [3, 2, 4], target = 6 gives [1, 2].
nums = [3, 3], target = 6 gives [0, 1].
nums = [1, 2, 3], target = 100 gives [-1, -1].

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free