Arrays and Iteration

Two-Sum with Hash Lookup

Walk the array once, storing seen values in a lookup table. When the complement is already present, the result indices are known.

Algorithm

Basic Implementation

basic.go 
package main

import "fmt"

func main() {
	arr := []int{2, 7, 11, 4, 5}
	target := 9
	seen := map[int]int{}
	first := -1
	second := -1
	for i, value := range arr {
		need := target - value
		if j, ok := seen[need]; ok {
			first = j
			second = i
			break
		}
		seen[value] = i
	}
	fmt.Printf("[%d, %d]\n", first, second)
}

Complexity

  • Time: O(n) average
  • Space: O(n)

Implementation notes

  • Go builds arr with []int{2, 7, 11, 4, 5} and allocates an empty map[int]int{} named seen, mapping a previously seen value to its index.
  • The loop is for i, value := range arr, so i is the zero-based index and value is a copy of the slice element for that iteration.
  • need := target - value is checked before insertion using Go's comma-ok form: if j, ok := seen[need]; ok { ... }. A missing key returns ok == false without needing a sentinel value.
  • On a hit, the source writes first = j and second = i, then breaks before recording the current value. On a miss, seen[value] = i inserts or replaces that key's index.
  • The trace records i=0 as a miss that stores {2: 0}, then i=1 as a hit for need 2 with result [0, 1].
  • fmt.Printf("[%d, %d]\n", first, second) prints deterministic index order; the map itself is never iterated for output.
execution replay The checked-in replay follows the language-neutral state table for `array-two-sum-hash`.
cross-language comparison This Go DSA version keeps the same data and final output as every other DSA book in this wave.