Dev Skills
Go·Go for coding rounds

Two sum with a map

The most-asked warm-up in any coding round, and the cleanest demonstration of why a map beats a nested loop.

Topic 24 of 98 · 5 min to read · 55 min to build
After this topic you can
  • Write a one-pass two sum with a map and state its O(n) time and space.
  • Explain why comma-ok is needed when 0 is a valid index.
  • Predict what goes wrong if you insert before you look up.

The problem

Given a slice of integers and a target, return the indices of the two numbers that add up to the target. Assume at most one answer, and you may not use the same element twice.

Tools you'll use here

  • slices.Sort(s) sorts a slice of numbers or strings in place, smallest first.
  • slices.SortFunc(s, func(a, b T) int { return cmp.Compare(a.x, b.x) }) sorts by your own rule; cmp.Compare returns -1, 0 or 1 for you.
  • Why slices.Sort works on any number or string type (generics, cmp.Ordered) is explained later in Generics, and container/heap in The standard library. Where a lesson uses a heap, it is an optional extra.

Brute force first

Check every pair with two nested loops: for each i, try every j > i and see if nums[i] + nums[j] == target.

O(n²) time, O(1) space. Fine for 100 numbers, far too slow for 1 million.

The approach

The brute force checks every pair: O(n²). Say it first, so they know you know it, then improve it.

For each number n, the partner you need is target - n. Keep a map from value to index of everything you have already walked past. If the partner is in the map, you are done. One pass, O(n) time and O(n) space.

two_sum.go
package main
import "fmt"
// twoSum returns the indices of the two numbers that add up to target.
// One pass: for each number, ask the map "have I already seen its partner?"
func twoSum(nums []int, target int) (int, int, bool) {
	seen := make(map[int]int, len(nums)) // value -> index
	for i, n := range nums {
		if j, ok := seen[target-n]; ok { // comma-ok: 0 is a valid index
			return j, i, true
		}
		seen[n] = i
	}
	return 0, 0, false
}
func main() {
	fmt.Println(twoSum([]int{2, 7, 11, 15}, 9)) // 0 1 true
	fmt.Println(twoSum([]int{3, 3}, 6))         // 0 1 true
	fmt.Println(twoSum([]int{1, 2, 3}, 100))    // 0 0 false
}

Dry run

nums = [2 7 11 15], target = 9, using the map solution:

inneed (target - n)seen before this stepaction
027{}7 not seen, store 2→0
172{2:0}2 found at index 0, return (0, 1)

Go-specific gotchas

  • Use comma-ok. seen[x] returns 0 when x is missing, and 0 is also a valid index. if j, ok := seen[x]; ok is the only correct test.
  • Check before you insert. Inserting first means [3] with target 6 would pair the element with itself.
  • Pre-size the map with make(map[int]int, len(nums)). It saves rehashing while it grows, and a reviewer notices.
  • Returning multiple values is more idiomatic than returning a []int{i, j} or -1, -1. The bool says "not found" without a magic number.
The short version
  • Say the O(n²) brute force, then trade space for time with a map: O(n).
  • Comma-ok, always, when zero is a meaningful value.
  • Look up the partner before inserting the current element.
Remember: When the question is "have I seen X before?", the answer is a map.
Build this before moving on
Count the pairs in a slice that sum to k (each pair once, duplicates allowed in the input) with one map and one pass. State the complexity before you run it.
Coding challenge · checked by tests
Write twoSum(nums []int, target int) (int, int, bool) that returns the indices i < j of the two numbers adding up to target, and true. If no pair exists, return 0, 0, false. Example: [2 7 11 15], target 9 → 0, 1, true.

Tab indents. Press Esc, then Tab, to leave the editor.

Then try these in your own editor
  1. 1The main task: Count the pairs in a slice that sum to k (each pair once, duplicates allowed in the input) with one map and one pass. State the complexity before you run it.
  2. 2Change two sum to return every pair of indices that sums to the target, with duplicates allowed in the input.
  3. 3Solve two sum on an already sorted slice with O(1) extra space.
  4. 4Dry run the map solution on nums = [3 2 4], target = 6. What does it return, and why does it not return (0, 0)?
  5. 5Write the brute-force version as a function twoSumBrute(nums []int, target int) (int, int, bool) and state its complexity.
Official documentation
Check yourselfTake the Go for coding rounds test