Problem overview
The method twoSum receives an Array[Int] named nums and an Int named target. It returns the indices of two different positions whose values add up to target, or Array(-1, -1) if there is no such pair. There is at most one valid pair, and the same index can't be used twice.
For nums = [2, 7, 11, 15] and target = 9, the values 2 and 7 at indices 0 and 1 sum to 9, so the answer is [0, 1].
The statement asks for O(n log n) time and O(n) extra space. That rules out checking every pair, which is O(n²), and points toward sorting plus binary search.
Approach: sort the pairs, then search for each complement
If a value x belongs to the answer, its partner must be target - x. In a sorted array, one specific value can be found in O(log n) by binary search, so one search per element costs O(n log n) in total, and the sort costs the same.
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 small [value, originalIndex] pairs instead of bare numbers. Every value then carries its index with it.
For the pair at sorted position i, the search looks only at positions i + 1 and later. Each pair of positions has a left member, so looking at the right side from every i covers every pair once, and starting at i + 1 also stops an element from being matched with itself. Two equal values at different positions can still match each other.
Step by step
- Create
sortedNums, an array with one slot for every element ofnums. Each slot will hold a two-element array. - Fill it: for each index
iinnums.indices, storeArray(nums(i), i), the value first and its original index second. - Sort
sortedNumsin place by the first element of each pair, so the pairs are ordered by value. - Loop over every position
iinsortedNums.indices. - For each
i, runbinarySearchon positionsi + 1to the end, looking for the valuetarget - sortedNums(i)(0). - If the search returns something other than
-1, return the original indices, which are the second elements of the two pairs. - If the loop finishes without a hit, return
Array(-1, -1).
The helper binarySearch is the usual search for an exact value, restricted to the range from firstIndex to lastIndex:
- Copy the two bounds into
var firstandvar last. - Loop while
first <= last. - Compute
middleasfirst + (last - first) / 2. - If the value at
middleequalsvalue, returnmiddle. - If it is smaller, the target can only be to the right, so set
first = middle + 1. - Otherwise set
last = middle - 1. - If the loop ends, return
-1.
The solution in Scala
class Solution {
def binarySearch(sortedNums: Array[Array[Int]], firstIndex: Int, lastIndex: Int, value: Int): Int = {
var first = firstIndex
var last = lastIndex
while (first <= last) {
val 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
}
def twoSum(nums: Array[Int], target: Int): Array[Int] = {
val sortedNums = Array.ofDim[Array[Int]](nums.length)
for (i <- nums.indices) {
sortedNums(i) = Array(nums(i), i)
}
sortedNums.sortInPlaceBy(arr => arr(0))
for (i <- sortedNums.indices) {
val j = binarySearch(sortedNums, i + 1, sortedNums.length - 1, target - sortedNums(i)(0))
if (j != -1) {
return Array(sortedNums(i)(1), sortedNums(j)(1))
}
}
return Array(-1, -1)
}
}
Scala details
Array.ofDim[Array[Int]](nums.length) creates an array of the given length whose elements are not set yet. For an array of arrays, each slot starts as null until the loop fills it. That is why the fill loop comes before the sort.
sortedNums(i)(0) reads slot i and then element 0 of the pair stored there. Scala indexes with parentheses, so there are no square brackets in the lookups.
sortInPlaceBy(arr => arr(0)) reorders the array itself and returns nothing useful, unlike sortBy, which returns a new array. The function you pass picks the sort key, here the value of each pair. The default ordering of Int does the comparison.
Method parameters can't be reassigned, so binarySearch copies firstIndex and lastIndex into the vars first and last. The form first + (last - first) / 2 gives the same midpoint as (first + last) / 2, but never adds the two indices, so it can't overflow an Int.
A return inside the for loop works, but a for loop over a collection is turned into a call with a function body, so the return is a non-local one. Scala 3.5 compiles it and prints a warning: "Non local returns are no longer supported; use boundary and boundary.break in scala.util instead". The program still runs and returns the right answer. A return directly inside a while loop, as in binarySearch, is not affected.
Complexity
Time: building the pairs is O(n), sorting is O(n log n), and the loop runs n binary searches that each take O(log n). The total is O(n log n).
Space: the array of pairs holds n small arrays, so it takes O(n) extra space. The search itself uses a few variables.
Edge cases and common mistakes
- Duplicates. For
[3, 3]andtarget = 6, the sorted pairs are(3, 0)and(3, 1). Ati = 0the search covers only position 1, finds 3, and the answer is[0, 1]. - Same index twice. For
[3, 2, 4]andtarget = 6, the value 3 would need a partner of 3. The only 3 is at the current position, which the search skips, so the answer is[1, 2](2 + 4). - Returning sorted positions. If you return
iandjinstead of the stored original indices, the answer refers to the sorted array and is wrong. - Negative numbers. Nothing special is needed.
[5, -2, 7]withtarget = 5gives[1, 2]. - No pair, one element or an empty array.
[1, 2, 3]withtarget = 10, and a one-element array, both give[-1, -1]. - Searching the whole array. Starting the search at 0 instead of
i + 1lets an element match itself, for example 3 withtarget = 6.
Testing
[2, 7, 11, 15]withtarget = 9gives[0, 1].[3, 2, 4]withtarget = 6gives[1, 2].[3, 3]withtarget = 6gives[0, 1].[3]withtarget = 6gives[-1, -1].
