LESSON 226 OF 338 · TWO POINTERS

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

GO · TWO POINTERS

Two Sum in Go, explained

Problem overview

The function twoSum receives a slice of integers, nums, and a target. It must return 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 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, and they add up to 9, so the answer is [0, 1]. The statement asks for O(n log n) time and O(n) extra space.

Approach: sort, then squeeze from both ends

Trying every pair costs O(n²). Sorting makes a faster scan possible. In an ascending list, put one pointer, first, on the smallest value and another, last, on the largest, and look at their sum:

If the sum equals target, the pair is found.
If the sum is too small, moving last left could only make it smaller, so the smallest value can't be part of any answer with the current largest or anything smaller. The only useful move is first++, to a larger value.
If the sum is too large, the same reasoning says last--.

Each step discards one candidate, so the scan takes at most n - 1 steps. The sort costs O(n log n), which dominates.

There is one catch: sorting moves values away from their positions, and the answer needs the original indices. So each value is stored together with its index as a two-element slice {value, index}, and the sort compares only the values.

Example with nums = [3, 9, -2, 5] and target = 3: the sorted pairs are {-2, 2}, {3, 0}, {5, 3}, {9, 1}. The sum of the ends, -2 + 9, is 7, which is too large, so last moves left. Then -2 + 5 equals 3, and the answer is the stored indices, [2, 3].

Step by step

Allocate sortedNums with make([][]int, len(nums)), one slot per element. Each slot will hold a {value, index} pair.
Fill it. Range over sortedNums and set element i to []int{nums[i], i}.
Sort by value with sort.Slice. Its second argument is a "less" function that takes two positions and returns whether the first element should come before the second, here comparing [0], the value.
Place the pointers with one statement: first at 0 and last at the final position.
Loop while first < last. When they meet, every candidate pair has been ruled out, and the same element is never used twice.
Compute sum of the two values, element [0] of each pair.
If sum == target, return the original indices, element [1] of each pair.
If the sum is smaller, do first++.
Otherwise the sum is larger, so do last--.
After the loop, return []int{-1, -1}.

The solution in Go

func twoSum(nums []int, target int) []int {
    sortedNums := make([][]int, len(nums))
    for i := range sortedNums {
        sortedNums[i] = []int{nums[i], i}
    }
    sort.Slice(sortedNums, func(i, j int) bool {
        return sortedNums[i][0] < sortedNums[j][0]
    })
    first, last := 0, len(sortedNums) - 1
    for first < last {
        sum := sortedNums[first][0] + sortedNums[last][0]
        if sum == target {
            return []int{sortedNums[first][1], sortedNums[last][1]}
        } else if sum < target {
            first++
        } else {
            last--
        }
    }
    return []int{-1, -1}
}

The Go details worth a closer look:

The sort package. sort.Slice needs import "sort" at the top of a standalone file. Without the import, the program doesn't compile.
A "less" function, not a comparator. The function passed to sort.Slice returns a bool, not a negative, zero or positive number. Its parameters are positions in the slice being sorted, so the body indexes sortedNums with them. It closes over sortedNums, which is allowed because function literals can use variables from the enclosing function.
Not stable. sort.Slice doesn't promise to keep equal elements in their original order. With duplicates, the two equal pairs may swap places, which only matters for the order of the two indices in the answer. sort.SliceStable keeps the order.
Slices of slices. Each element of sortedNums is its own small slice. That is simple, though a struct with two fields would be clearer in a larger program.
Short declaration of two variables. first, last := 0, len(sortedNums) - 1 declares both at once.
If / else if / else. The three branches cover equal, smaller and larger. Go has no parentheses around conditions, and else must sit on the same line as the closing brace.
Index order in the answer. The index of the smaller value comes first: for [7, 2] and target 9, the function returns [1, 0].

Complexity

Time: O(n log n). Building the pairs is O(n), sorting is O(n log n), and the two-pointer scan is O(n), since every step moves one pointer and they can travel at most n positions in total.

Space: O(n). There is one small slice per element. A hash map would give O(n) time with the same space, but this lesson practises sorting with two pointers.

Edge cases and common mistakes

No pair. [1, 2, 3] with target 100 returns [-1, -1].
Empty or one-element input. first < last is false at once, so the function returns [-1, -1].
Equal values. [3, 3] with target 6 returns [0, 1], since the two 3s sit at different indices.
Same element twice. [3, 4] with target 6 returns [-1, -1], because the pointers never cross over to use one element for both ends.
Negative numbers. The reasoning about sorted sums doesn't depend on signs: [-3, 4, 3, 90] with target 0 returns [0, 2].
Returning sorted positions. first and last are positions in the sorted slice. The answer comes from element [1] of each pair.
Returning a difference from the less function. It must return a bool, so return a - b doesn't compile.

Testing

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

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

Start learning free