Start learning free

LESSON 230 OF 348 · TWO POINTERS

Two Sum in Kotlin: 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
    Ctrl + Enter to check

    KOTLIN · TWO POINTERS

    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] if there is no such pair. There is at most one valid pair, 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 is more than enough to sort a copy of the data, and sorting is what makes this lesson's idea possible.

    Approach: sort, then move two pointers inward

    Checking every pair of indices takes O(n²) time. Sorting lets you do much better. In an ascending array, put one pointer at the smallest value and one at the largest, and look at their sum:

    • If the sum equals target, the pair is found.
    • If the sum is too small, the left value can't be part of any answer with the current right value or anything smaller, so move the left pointer one step right to get a larger value.
    • If the sum is too large, move the right pointer one step left to get a smaller value.

    Every step discards one element for good, so the pointers meet after at most n - 1 steps. The scan is O(n) and the sort is O(n log n), so the sort sets the total.

    Sorting has a catch: the answer needs the original indices, and sorting moves values around. The fix is to sort small pairs, each holding a value and the index it came from. The pair travels with its value wherever the sort puts it.

    Take nums = [3, 9, -2, 5] and target = 3. The pairs sorted by value are (-2, 2), (3, 0), (5, 3), (9, 1). The pointers start on -2 and 9, whose sum is 7. That is too big, so the right pointer moves to 5. Now -2 + 5 = 3, which matches, and the answer is the stored indices [2, 3].

    A hash map solves the same problem in O(n) time, and a binary search per element is another sorted-array option. This lesson practises the two-pointer scan.

    Step by step

    1. Create the pairs array. sortedNums has one row per element, and each row is an IntArray(2) holding a value and its index.
    2. Fill it. Row i becomes (nums[i], i), so the original position is recorded before anything moves.
    3. Sort the rows by value. sortBy { it[0] } uses the first element of each row as the key, and the second element just rides along.
    4. Place the pointers. first starts at 0 and last at the final position. Both are var because they change.
    5. Loop while first < last. When they meet, no unchecked pair is left, and two pointers on the same spot would reuse one index.
    6. Add the two values. Index 0 of a row is the value, so the sum is sortedNums[first][0] + sortedNums[last][0].
    7. On a match, return the original indices. They are in index 1 of each row, not the pointer positions.
    8. Too small: first++. Only a larger left value can raise the sum.
    9. Too large: last--. Only a smaller right value can lower the sum.
    10. Return [-1, -1] after the loop, because the loop only ends without returning when every candidate has been ruled out.

    The solution in Kotlin

    class Solution {
    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] }

        var first = 0
        var last = sortedNums.size - 1
        while (first < last) {
            val sum = sortedNums[first][0] + sortedNums[last][0]
            if (sum == target) {
                return intArrayOf(sortedNums[first][1], sortedNums[last][1])
            } else if (sum < target) {
                first++
            } else {
                last--
            }
        }
        return intArrayOf(-1, -1)
    }
}

    The Kotlin details worth a closer look:

    • Array(size) { init }. This constructor calls the lambda once for each position and builds the array from the results. Each call produces a separate IntArray(2), so the rows don't share storage. The loop then replaces each placeholder row with the real pair.
    • Array<IntArray> and intArrayOf. sortedNums is an array of primitive int arrays, so sortedNums[first][0] is a plain Int. The val only fixes which array the name refers to; the rows can still be replaced.
    • sortBy sorts in place. On an array, sortBy { it[0] } reorders the array itself and returns nothing useful. sortedBy returns a new list and leaves the array alone. The sort is stable, so rows with equal values keep their original order.
    • it. In a lambda with one parameter, Kotlin names that parameter it automatically. Here it is one row, an IntArray.
    • The empty array. With nums.size == 0, last is -1, the condition first < last is false at once, and the function returns [-1, -1]. Nothing is read from the empty array.
    • Int overflow. Int is 32 bits and wraps silently. For two values of 2000000000, the sum is -294967296, not 4000000000. If a test target could match a wrapped sum, the function would report a false pair; the lesson's tests don't do this.
    • No semicolons. The if/else if/else chain is a statement here, and each branch contains a single statement.

    Complexity

    Time: O(n log n). Building the pairs is O(n). Sorting is O(n log n). The loop moves one pointer every iteration, so it runs at most n - 1 times, which is O(n). The sort dominates.

    Space: O(n). There is one two-element array per input value, plus a few integers for the pointers and the sum. The input array isn't modified.

    Edge cases and common mistakes

    • Returning pointer positions. first and last are positions in the sorted array. The answer is in [1] of those rows. For [3, 9, -2, 5] with target 3, the pointers end at positions 0 and 2, but the answer is [2, 3].
    • Using first <= last. When both pointers are on one element, that element would be paired with itself. For [3, 4] and target 6, the function would answer [0, 0] instead of [-1, -1].
    • Equal values. [3, 3] with target 6 returns [0, 1]. The two 3s are different elements with different indices.
    • Index order. The smaller value's index comes first. For [7, 2] and target 9 the result is [1, 0].
    • Sorting nums directly. That loses the original positions. The pairs are what keep them.
    • Fewer than two elements. An empty array or a single element returns [-1, -1].

    Testing

    • nums = [2, 7, 11, 15], target = 9 gives [0, 1].
    • nums = [3, 9, -2, 5], target = 3 gives [2, 3].
    • nums = [3, 3], target = 6 gives [0, 1].
    • nums = [3, 4], target = 6 gives [-1, -1].
    • nums = [], target = 9 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