Start learning free

LESSON 247 OF 338 · BINARY SEARCH

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


SOLVE IT YOURSELF
Ctrl + Enter to check

GO · BINARY SEARCH

Two Sum in Go, explained

Problem overview

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

In the example, 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 sets a budget of O(n log n) time and O(n) extra space. That rules out checking every pair, which is O(n²), and points toward sorting.

Approach: sort, then binary search for each complement

If a value x is part of the answer, its partner must be exactly target - x, the complement. Looking up a particular value in a sorted slice takes O(log n) with binary search, so one search per element costs O(n log n) in total, the same order as the sort itself.

Sorting causes one problem: it moves values away from their original positions, and the answer must use the original indices. The fix is to sort small pairs [value, original index] instead of bare values. Each value carries its index with it.

The search for the partner of the pair at sorted position i looks only at positions i+1 and beyond. Any two positions form a pair whose left member is found when the loop reaches it, so looking to the left would only repeat work. It also guarantees that an element is never matched with itself.

Example with nums = [3, 9, -2, 5] and target = 3. The sorted pairs are [-2, 2], [3, 0], [5, 3], [9, 1]. At position 0 the value is -2, so the search looks for 5 among positions 1 to 3 and finds it at position 2. The function returns the original indices stored in those two pairs: [2, 3].

A hash map would solve Two Sum in O(n) time. This lesson practises binary search, so it uses sorting and a search instead.

Step by step

  1. Write a binary search helper over the sorted pairs. It takes the pairs, the inclusive range first to last to search, and the value to find, and returns the position of the match or -1.
  2. Loop while the range is non-empty, first <= last.
  3. Take the middle as first + (last-first)/2 and compare the pair's value (its element 0) with value.
  4. Return, move right, or move left. A match returns middle; a smaller middle value means first = middle + 1; a larger one means last = middle - 1. After the loop, return -1.
  5. In twoSum, build the pairs. Make a slice of the same length as nums and store []int{nums[i], i} in each slot.
  6. Sort the pairs by value with sort.Slice, comparing the first elements.
  7. Loop over the sorted positions. For each i, search positions i+1 to len(sortedNums)-1 for target - sortedNums[i][0].
  8. On a hit, return the original indices (element 1 of both pairs), not the sorted positions.
  9. Return []int{-1, -1} after the loop.

The solution in Go

func binarySearch(sortedNums [][]int, first, last, value int) int {
	for first <= last {
		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
}

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]
	})

	for i := range sortedNums {
		j := binarySearch(sortedNums, i+1, len(sortedNums)-1, target-sortedNums[i][0])
		if j != -1 {
			return []int{sortedNums[i][1], sortedNums[j][1]}
		}
	}
	return []int{-1, -1}
}

Go details in this code

  • Pairs as []int. The slice of slices [][]int holds a two-element slice per number: index 0 is the value, index 1 the original position. A small struct would be clearer in a larger program, but a two-element slice is enough here.
  • make([][]int, len(nums)) creates the outer slice with every inner slice still nil; the loop then fills each slot.
  • for i := range sortedNums with one variable gives the indices, which is all the loops need.
  • sort.Slice. It needs the sort package and sorts in place using a less function that receives two indices. It is not guaranteed to keep equal elements in their original order, which is harmless here because equal values carry their own indices.
  • Parameters sharing a type. first, last, value int declares three int parameters. The function changes first and last, which are copies, so the caller's variables are untouched.
  • The result follows sorted order. The first index returned belongs to the smaller value, so [4, 2] with target 6 gives [1, 0].

Complexity

Time: O(n log n). Building the pairs is O(n), sorting is O(n log n), and the loop makes up to n binary searches of O(log n) each.

Space: O(n). The pairs hold one small slice per element.

Edge cases and common mistakes

  • Equal values. For [3, 3] and target = 6 the sorted pairs are [3, 0] and [3, 1]. The first one searches position 1 for 3 and finds it, returning [0, 1]. Two different indices holding equal values are allowed.
  • The same element twice. For [3] and target = 6, the search range 1..0 is empty, so the result is [-1, -1]. Searching from position 0 would wrongly match the element with itself.
  • No pair. For [1, 2] and target = 10 the result is [-1, -1].
  • Returning sorted positions. The positions in the sorted slice are meaningless to the caller. Always return element 1 of the pairs.
  • Sorting nums directly. The original indices are lost, and they can't be recovered afterwards.
  • Binary search on unsorted data. The helper is correct only because the pairs are sorted first.
  • Empty slice. Nothing is searched, and the function returns [-1, -1].

Testing

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