GopherForgeA WORKBENCH FOR GO

Junior · Algorithms

Two sum and index ownership

Find two distinct indexes whose values sum to a target.

Try explaining this aloud before opening the answer. State your assumptions and trace a boundary case.

ALGORITHM LAB · STEP THROUGH THE INVARIANT

[2, 7, 11, 15], target 9

STEP 1 / 4

Search before insert

Input
20
71
112
153

Only earlier indexes are in seen.

Computed traces for these inputs. Indexes identify cell positions; active cells are labeled as well as highlighted. Compare a boundary case using the scenario selector. No code is sent to a server.

EXAMPLE · FRAGMENT UNLESS A COMPLETE PROGRAM IS SHOWN

go
func TwoSum(xs []int, target int) (int, int, bool) {
	seen := make(map[int]int)
	for j, x := range xs {
		if i, ok := seen[target-x]; ok {
			return i, j, true
		}
		seen[x] = j
	}
	return 0, 0, false
}
Reveal a strong answer

  1. Scan once and map each previously seen value to an index. Before storing the current value, look for target-current; that ordering prevents using the current index twice.

  2. Store and return indexes, not just values, because duplicates can form the answer. For [3,3] and target6, the second element finds the first. Define behavior when no pair exists or several pairs qualify.

  3. Hash lookup gives expected constant time, not a universal worst-case guarantee. Bound input and consider integer overflow before computing the complement when values are untrusted or use the full int range.

Common trap

Inserting the current element before lookup may return the same index twice.

Complexity & use

Expected O(n) time and O(n) storage, assuming complement arithmetic fits int.

Try it

Trace [2,7,11,15] with target9 and then [3,3] with target6.

Worked solution

The first case stores2→0, then7 finds2 and returns(0,1). The second stores the first3, and the second3 finds index0. Test no result and duplicate values independently.

Change the constraint

If the input is sorted, when would two pointers be preferable to a map?

How did you do?

Self-assessment, not a compiler pass or interview score. Explain the reasoning unaided before marking understood.

Not marked. Progress stays on this browser, separate from course completion.

Primary references

Checked 2026-10-20. Use documentation for your pinned runtime, driver and tool version.