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] when no such pair exists. There is at most one solution, and the same 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 sets a budget of O(n log n) time and O(n) extra space.
Approach: sort the pairs, then search for each complement
Checking every pair of indices takes O(n²). The faster idea starts from an observation: if a value x is part of the answer, its partner must be exactly target - x. Finding a given value in a sorted array is a binary search, O(log n), so one search per element gives O(n log n) in total, and sorting costs the same.
Sorting has a catch: it moves values away from their original positions, and the answer needs the original indices. So the lesson sorts [value, originalIndex] pairs instead of bare numbers. Each value carries its index wherever the sort puts it.
The partner of the pair at position i is searched only to its right, from i + 1 on. Every two positions have a left one and a right one, so the pair is found when the loop reaches the left one. Starting at i + 1 also stops an element from pairing with itself.
Try nums = [3, 9, -2, 5] with target = 3. The sorted pairs are [[-2, 2], [3, 0], [5, 3], [9, 1]]. At position 0 the value is -2, so the search looks for 5 in positions 1 to 3. The midpoint, position 2, holds 5, so the result is built from the original indices 2 and 3: [2, 3].
Other approaches exist: a dictionary of seen values gives O(n), and this lesson practises binary search instead.
Step by step
- Create
sortedNumsas avarof type[[Int]], empty at first. It will hold the pairs. - Fill it in a loop over
0..<nums.count, appending[nums[i], i]. The value is first so that ordering by the first element orders by value. - Sort it with
sortedNums.sort { $0[0] < $1[0] }. The closure is needed because arrays of arrays have no built-in ordering. - Loop over the positions of the sorted pairs. Each one is tried as the first number of the answer.
- Search for the complement. Call
binarySearch(sortedNums, i + 1, sortedNums.count - 1, target - sortedNums[i][0])and keep the result inj. - On a hit, when
j != -1, return[sortedNums[i][1], sortedNums[j][1]], the original indices. - After the loop, return
[-1, -1]. - Write the helper
binarySearchabovetwoSum. Its parameters are constants, so the first lines copy the bounds intovar firstandvar last. - Loop while
first <= last, that is, while the range is not empty. - Take the midpoint as
first + (last - first) / 2. - If the value at the midpoint equals
value, returnmiddle. - If it is smaller, set
first = middle + 1, discarding the lower half. - Otherwise, set
last = middle - 1, discarding the upper half. - Return
-1after the loop: no partner exists in that range.
The solution in Swift
class Solution {
func binarySearch(_ sortedNums: [[Int]], _ firstIndex: Int, _ lastIndex: Int, _ value: Int) -> Int {
var first = firstIndex
var last = lastIndex
while first <= last {
let middle = first + (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
}
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var sortedNums: [[Int]] = []
for i in 0..<nums.count {
sortedNums.append([nums[i], i])
}
sortedNums.sort { $0[0] < $1[0] }
for i in 0..<sortedNums.count {
let j = binarySearch(sortedNums, i + 1, sortedNums.count - 1, target - sortedNums[i][0])
if j != -1 {
return [sortedNums[i][1], sortedNums[j][1]]
}
}
return [-1, -1]
}
}
The Swift details worth a closer look:
- Parameters are constants. Assigning to
firstIndexwould be a compile error, so the helper copies it intovar first. - Arrays of arrays.
[[Int]]is an array whose elements are arrays.sortedNums[middle][0]reads the value of a pair and[1]reads its original index. Arrays are value types, sosortedNumsis copied logically when passed tobinarySearch, but Swift shares the storage until someone writes to it, so the call costsO(1). - The sorting closure.
$0and$1are the two elements being compared, and the closure returnstruewhen the first should come before the second.sortchanges the array in place, which is whysortedNumsmust bevar. - The range
0..<nums.countexcludes the upper end. It is empty when the array is empty, so the loop simply does not run. - Overflow traps. The subtraction
target - sortedNums[i][0]uses 64-bitInt. With ordinary values it is exact; with extreme values such asInt.minit would stop the program instead of wrapping.
Complexity
Time: O(n log n). Building the pairs is O(n), sorting is O(n log n), and the loop makes at most n binary searches that each cost O(log n).
Space: O(n). sortedNums holds one small array per element. The search itself uses a few integers.
Edge cases and common mistakes
- Fewer than two elements. For an empty array or a single element no search succeeds, and the method returns
[-1, -1]. - Equal values.
[3, 3]with target 6 returns[0, 1]: different indices holding equal numbers are allowed. - Pairing an element with itself.
[3, 4]with target 6 returns[-1, -1]. A search starting at position 0 would find the same 3 and answer[0, 0]. - Sorted positions instead of original indices. After the sort,
iandjrefer to sorted positions. The answer comes from the second element of each pair. - Index order. The pair with the smaller value comes first, so
[7, 2]with target 9 returns[1, 0]. - Using
first < last. A range with one element would never be checked, and[2, 7]with target 9 would wrongly give[-1, -1].
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 = [1, 2, 3],target = 100gives[-1, -1].nums = [],target = 5gives[-1, -1].
