LESSON 251 OF 348 · BINARY SEARCH

Two Sum in Kotlin: O(n log n) with Sorting and Binary Search

Practice O(n log 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 14

Guided

Ctrl + Enter to check

KOTLIN · BINARY SEARCH

Two Sum in Kotlin, explained

Problem overview

The function twoSum receives an IntArray called nums and an Int called target. It returns the indices of two different positions whose values add up to target, or [-1, -1] when there is no such pair. There is at most one solution, and one index can't be used twice, although two equal values at different indices are fine.

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

The statement allows O(n log n) time and O(n) extra space. That rules out trying every pair of indices, which is O(n²), and points toward sorting.

Approach: sort the pairs, then search for each complement

If a value x belongs to the answer, its partner is exactly target - x, the complement. Finding a specific value in a sorted array is a binary search, O(log n), so one search per element costs O(n log n) in total, the same as the sort.

Sorting has a catch: 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. Each value travels with its index, wherever the sort puts it.

The search for the partner of position i only looks at positions after i. Any pair has a left member, and the loop reaches that member first, so looking left would repeat work. Starting at i + 1 also keeps an element from pairing with itself.

Take nums = [3, 9, -2, 5] and target = 3. The sorted pairs are [-2, 2], [3, 0], [5, 3] and [9, 1]. At position 0 the value is -2, so the search looks for 5 among positions 1 to 3. The first midpoint, position 2, holds 5, so the function returns the stored indices of positions 0 and 2: [2, 3].

Other solutions exist. A hash map of the values seen so far gives O(n) time. This lesson practises binary search, so it searches for each complement directly.

Step by step

Create the pair array. Array(nums.size) { IntArray(2) } builds one two-element IntArray per input element. These are placeholders that the next step overwrites.
Fill each row with intArrayOf(nums[i], i), looping over nums.indices. The value goes first so that ordering by the first element orders by value.
Sort with sortedNums.sortBy { it[0] }. After this the values are ascending, which binary search needs.
Loop over every position of the sorted array. Each pair is tried as the first element of the answer.
Search to the right for target - sortedNums[i][0] by calling the helper binarySearch with the range i + 1 to the last position.
On a hit, return the original indices, the second element of each pair, not the sorted positions.
Fall back to intArrayOf(-1, -1) when the loop ends without a match.
Write the helper's signature. It takes the pairs, the inclusive range firstIndex to lastIndex and the value to find. Parameters are read-only in Kotlin, so copy the bounds into var first and var last.
Loop while the range is non-empty: first <= last.
Take the midpoint as first + (last - first) / 2, which never exceeds last.
On equality, return middle.
If the middle value is too small, discard the left half with first = middle + 1.
Otherwise discard the right half with last = middle - 1.
Return -1 once the range is empty.

The solution in Kotlin

class Solution {
    fun binarySearch(sortedNums: Array<IntArray>, 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
    }

    fun twoSum(nums: IntArray, target: Int): IntArray {
        val sortedNums = Array(nums.size) { IntArray(2) }
        for (i in nums.indices) {
            sortedNums[i] = intArrayOf(nums[i], i)
        }
        sortedNums.sortBy { it[0] }

        for (i in sortedNums.indices) {
            val j = binarySearch(sortedNums, i + 1, sortedNums.size - 1, target - sortedNums[i][0])
            if (j != -1) {
                return intArrayOf(sortedNums[i][1], sortedNums[j][1])
            }
        }
        return intArrayOf(-1, -1)
    }
}

The Kotlin details worth a closer look:

Array<IntArray>. This is an array whose elements are IntArrays, each holding a primitive int[] on the JVM. The constructor form Array(n) { ... } runs the lambda once per index, so every row is a separate object.
sortBy sorts in place. It reorders the array itself by the key the lambda returns (it[0], the value). It is stable, so rows with equal values keep their original relative order. It returns Unit; the version that returns a new list is sortedBy.
Two-dimensional indexing. sortedNums[i][1] first takes row i, then element 1 of that row, the stored original index.
indices. nums.indices is the range 0 until nums.size, so the loops cannot run past the end. For an empty array they run zero times.
if / else if with return. Each branch of the helper either returns or moves a bound, and the final return -1 covers the empty-range case.

Complexity

Time: O(n log n). Building the pairs is O(n) and sorting is O(n log n). The loop makes at most n binary searches, each halving its range, so each is O(log n). Both parts stay within O(n log n).

Space: O(n). The pair array holds one two-element array per input element. The search itself uses a few integers.

Edge cases and common mistakes

Fewer than two elements. An empty array skips the loop, and a single element searches an empty range (i + 1 is past the end). Both return [-1, -1].
Equal values. [3, 3] with target 6 returns [0, 1]. The two 3s are different positions, and the search for the second starts at position 1.
Pairing an element with itself. [3, 4] with target 6 returns [-1, -1]. Searching from position 0 would find the same 3 and answer [0, 0].
Returning sorted positions. i and j are positions in the sorted array. The answer comes from the second element of each pair.
Using first < last. When the range holds one element, first equals last and a strict comparison skips it, so [2, 7] with target 9 would wrongly give [-1, -1].
Index order. The index of the smaller value comes first. For [7, 2] and target 9 the function returns [1, 0].
Overflow. Int arithmetic wraps silently, so target - sortedNums[i][0] can produce a wrong complement when the numbers are near the limits of Int. With nums = [294967296, 2000000000] and target = -2000000000, the subtraction wraps around to 2000000000, the search finds it, and the function returns [0, 1] although the real sum is 2294967296. The lesson's tests use small values; computing the complement as a Long would avoid the problem.

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 = [], target = 5 gives [-1, -1].

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

Start learning free