LESSON 254 OF 415 · TWO POINTERS

Two Sum in Swift: 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

SWIFT · TWO POINTERS

Two Sum in Swift, explained

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 one index can't be used twice.

For nums = [2, 7, 11, 15] and target = 9, the values at indices 0 and 1 are 2 and 7, which sum to 9, so the answer is [0, 1].

The statement asks for O(n log n) time and O(n) extra space, which rules out comparing every pair, an O(n²) approach.

Approach: sort, then squeeze from both ends

Suppose the values are sorted in ascending order. Put one pointer, first, on the smallest value and another, last, on the largest, and look at their sum:

If it equals target, the pair is found.
If it is too small, then even the largest remaining value can't make first reach the target, so first belongs to no answer. Move it right.
If it is too large, then even the smallest remaining value is too much for last, so move last left.

Each step discards one candidate for good, so the scan takes at most n - 1 steps. The sort dominates the cost, and it gives the O(n log n) bound.

There's one catch. Sorting moves the values, but the answer needs their original positions. The fix is to sort (value, originalIndex) tuples instead of bare numbers, so every value keeps its index with it.

On the example, the sorted pairs are (2, 0), (7, 1), (11, 2), (15, 3). The first sum is 2 + 15 = 17, which is too large, so last moves left. Then 2 + 11 = 13 is still too large. Then 2 + 7 = 9 matches, and the original indices are 0 and 1.

A hash map from value to index would solve the problem in O(n) time, and a brute-force double loop in O(n²). This lesson practises sorting and two pointers.

Step by step

Create the array of pairs. sortedNums is a var array of (Int, Int) tuples, filled at first with (0, 0) placeholders, one per element of nums.
Fill it. For each position i, store (nums[i], i): the value first, then where it came from.
Sort by value. Tuples can't be sorted without telling Swift how to compare them, so sort gets a closure comparing the first fields: $0.0 < $1.0.
Place the pointers. first is 0 and last is sortedNums.count - 1.
Loop while first < last. When the pointers meet, no pair is left to test.
Add the two values (the .0 fields) into sum.
On a match, return the original indices, the .1 fields of the two pairs.
If the sum is too small, increase first.
Otherwise, the sum is too large, so decrease last.
After the loop, return [-1, -1].

The solution in Swift

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var sortedNums = [(Int, Int)](repeating: (0, 0), count: nums.count)
        for i in 0..<nums.count {
            sortedNums[i] = (nums[i], i)
        }
        sortedNums.sort { $0.0 < $1.0 }

        var first = 0
        var last = sortedNums.count - 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 += 1
            } else {
                last -= 1
            }
        }
        return [-1, -1]
    }
}

Swift details worth knowing:

Tuples. A tuple like (Int, Int) has no names here, so its parts are read as .0 and .1. The array is created with [(Int, Int)](repeating: (0, 0), count: nums.count), which gives it the right length so that sortedNums[i] = ... is allowed.
The sort closure. In { $0.0 < $1.0 }, $0 and $1 are the two pairs being compared, and .0 picks the value from each. Swift's sort works in place, so the array must be a var. Pairs whose values are equal may end up in either order; the code doesn't depend on which.
Range 0..<nums.count. It excludes the upper end, so i is always a valid index. For an empty array the range is empty and the loop body never runs.
Arrays are values. sortedNums is a separate copy, so sorting it leaves the caller's nums untouched.

Complexity

Time: O(n log n). Building the pairs is O(n), sorting is O(n log n), and the two-pointer scan moves one pointer per step and ends after at most n - 1 steps.

Space: O(n). sortedNums holds one tuple per element.

Edge cases and common mistakes

Fewer than two elements. With an empty array, last is -1 and with one element first and last are both 0. In both cases first < last is false, and the method returns [-1, -1].
Equal values. [3, 3] with target 6 returns [0, 1]. The two 3s are different positions, so they are a valid pair.
The same element twice. [3, 4] with target 6 gives [-1, -1]. The pointers never cross, so one element is never paired with itself.
Returning sorted positions. first and last are positions in the sorted array. The answer comes from the .1 fields.
Index order. The pair holding the smaller value comes first. For [7, 2] and target 9, the answer is [1, 0].
Negative numbers. They need no special handling, because the argument for moving a pointer only relies on the sort order.

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 = [7, 2], target = 9 gives [1, 0].
nums = [1, 2, 3], target = 100 gives [-1, -1].

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

Start learning free