LESSON 253 OF 414 · TWO POINTERS

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

SCALA · TWO POINTERS

Two Sum in Scala, explained

Problem overview

The method twoSum(nums: Array[Int], target: Int) must return the indices of two different positions whose values add up to target, or Array(-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 asks for O(n log n) time and O(n) extra space. That rules out trying every pair, which takes O(n²).

Approach: sort, then squeeze from both ends

If the values are sorted, a pair can be found with two pointers: first at the smallest value and last at the largest. Look at their sum:

If it equals target, the pair is found.
If it is too small, nothing paired with the value at first can reach the target, because the largest available partner was already too small. Move first right to a larger value.
If it is too large, the value at last is too big for every remaining partner, because the smallest available partner is already too large. Move last left.

Each step discards one value for good, so the scan takes at most n - 1 steps. Sorting costs O(n log n) and dominates the total.

Sorting has a catch: it moves values away from their positions, and the answer needs the original indices. The fix is to sort (value, index) pairs instead of bare values, so every value carries its index with it.

A hash map that remembers the values seen so far solves Two Sum in O(n) time. This lesson uses sorting and two pointers instead.

Step by step

Allocate the pairs. Array.ofDim[(Int, Int)](nums.length) makes an array of tuples, one slot per element. It is a var because the sorted version is assigned back to it.
Fill it. Loop over nums.indices and store (nums(i), i) in slot i.
Sort by value. sortBy(_._1) orders the tuples by their first component. It returns a new array, so the result is assigned back to sortedNums.
Place the pointers. first is 0 and last is sortedNums.length - 1.
Loop while first < last. When the pointers meet, every pair has been ruled out, and a value is never paired with itself.
Add the two values. In each tuple, _1 is the value and _2 is the original index.
On a match, return the original indices sortedNums(first)._2 and sortedNums(last)._2, not the sorted positions.
Too small: first += 1.
Too large: last -= 1.
No match: after the loop, Array(-1, -1) is the last expression and the method's result.

The solution in Scala

class Solution {
    def twoSum(nums: Array[Int], target: Int): Array[Int] = {
        var sortedNums = Array.ofDim[(Int, Int)](nums.length)
        for (i <- nums.indices) {
            sortedNums(i) = (nums(i), i)
        }
        sortedNums = sortedNums.sortBy(_._1)

        var first = 0
        var last = sortedNums.length - 1
        while (first < last) {
            val sum = sortedNums(first)._1 + sortedNums(last)._1
            if (sum == target) {
                return Array(sortedNums(first)._2, sortedNums(last)._2)
            } else if (sum < target) {
                first += 1
            } else {
                last -= 1
            }
        }
        Array(-1, -1)
    }
}

On nums = [3, 9, -2, 5] with target = 3, the sorted pairs are (-2,2) (3,0) (5,3) (9,1). The first sum is -2 + 9 = 7, too large, so last moves left. Then -2 + 5 = 3 matches, and the method returns [2, 3], the original indices.

The Scala details worth knowing:

Tuples. (nums(i), i) builds a (Int, Int). Its parts are read with _1 and _2, which count from 1.
sortBy(_._1). The underscore stands for the tuple being examined, and ._1 picks its value. The sort is stable, so equal values keep their original relative order.
sortBy doesn't sort in place. Calling it without assigning the result would leave sortedNums unsorted.
return in a loop. The early return leaves the method from inside the while. The final Array(-1, -1) needs no return, since the last expression of a block is its value.
Which index comes first. The index of the smaller value comes first. For [7, 2] and target 9 the result is [1, 0].

Complexity

Time: O(n log n). Building the pairs is O(n), sorting is O(n log n), and the pointers move at most n - 1 times in total.

Space: O(n). The array of pairs holds one tuple per element, and the sorted copy is another array of the same size. Both are linear.

Edge cases and common mistakes

Fewer than two elements. An empty array gives last = -1, and a single element gives first == last. The loop never runs in either case, and the method returns [-1, -1].
Equal values. [3, 3] with target 6 returns [0, 1]: two different positions that hold the same value are allowed.
The same element twice. [3, 4] with target 6 returns [-1, -1]. The loop condition first < last keeps the pointers on different elements, so the 3 is not paired with itself.
Returning sorted positions. The positions first and last refer to the sorted array. The answer is in the _2 fields.
Forgetting to assign the sort. sortBy returns a new array.
Overflow. Int is 32 bits and wraps silently, so for large values the sum of two elements can wrap. For instance, 2000000000 + 2000000000 evaluates to -294967296 in Int. Adding as Long avoids that.

Testing

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

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

Start learning free