Two Sum II - Input Array Is Sorted

Start dumb: try every pair

Two positions, one target sum — the honest first idea is the double loop: for every i, try every j > i and test numbers[i] + numbers[j] == target. That’s O(n²) comparisons, and it treats the input as an arbitrary bag of numbers.

Find the bottleneck

The brute force ignores the one gift this problem hands you: the array is sorted. Sortedness makes the pair sum predictable — you always know which direction a pointer move pushes it. Testing pairs in arbitrary order throws that signal away and re-learns nothing from each failed comparison.

The optimal shape

Two pointers converge from the ends of the array:

1. Compute the sum of the two pointed-at values.
2. Exact hit → done (report 1-based positions).
3. Too small → only moving left rightward can raise the sum.
4. Too big → only moving right leftward can lower it.

Each step retires one value, so the pointers cross after at most n − 1 moves — O(n) time and, unlike the hash-map Two Sum, O(1) space: sortedness replaces the lookup table. Watch the window between the pointers in the player below — it only ever shrinks, never re-expands. That one-way collapse is the proof.

Watch it think

Step through the default input, then probe the edges: duplicates (3,3 | 6), negatives (-3,3,4 | 0), an impossible target (1,2,3 | 100), or an unsorted list — the player will tell you why sortedness is non-negotiable.

1fun twoSum(numbers: IntArray, target: Int): IntArray {
2    var left = 0
3    var right = numbers.lastIndex
4    while (left < right) {
5        val sum = numbers[left] + numbers[right]
6        when {
7            sum == target -> return intArrayOf(left + 1, right + 1)
8            sum < target -> left++
9            else -> right--
10        }
11    }
12    return intArrayOf(-1, -1)
13}