Solving Two Sum Problem in Go: Step-by-Step Guide

Introduction to the Two Sum Problem

The Two Sum problem is one of the most iconic algorithmic challenges in computer science. Frequently featured as the first problem on platforms like LeetCode, it asks a deceptively simple question: given an array of integers and a target value, find two numbers in the array that add up to the target, and return their indices.

While the problem statement is short, it serves as an excellent gateway into algorithmic thinking, hash-based lookups, and time-space tradeoffs. In this tutorial, we'll explore how to solve it in Go (Golang), starting from a naive approach and progressing to an optimal solution.

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target. You may assume that each input has exactly one solution, and you may not use the same element twice.

For example, given nums = [2, 7, 11, 15] and target = 9, the function should return [0, 1] because nums[0] + nums[1] = 2 + 7 = 9.

Why the Two Sum Problem Matters

The Two Sum problem is more than just an interview warm-up. It teaches several foundational concepts that appear repeatedly in real-world software engineering:

• Hash map usage: Demonstrates how hash-based data structures can reduce lookup time from linear to constant.
• Time-space tradeoffs: Shows how sacrificing memory can dramatically improve runtime performance.
• Single-pass algorithms: Introduces the idea of solving problems while iterating only once through the data.
• Edge case handling: Forces developers to consider duplicate values, negative numbers, and zero.

In production systems, similar patterns emerge whenever you need to find complementary records, deduplicate entries, or detect matching pairs in streaming data.

The Brute Force Approach

The most intuitive solution is to check every possible pair of numbers in the array. For each element, iterate through every other element and check if their sum equals the target.

Implementation

package main

import "fmt"

func twoSumBruteForce(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i]+nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}

func main() {
    nums := []int{2, 7, 11, 15}
    target := 9
    result := twoSumBruteForce(nums, target)
    fmt.Println(result) // Output: [0 1]
}

Complexity Analysis

The brute force approach has a time complexity of O(n²) because of the nested loops. The space complexity is O(1) since no additional data structures are used. For small arrays, this is acceptable, but it becomes prohibitively slow as the input grows.

The Optimal Hash Map Approach

The key insight for optimization is recognizing that for each number x, we need to find a complementary number target - x. Instead of scanning the array for this complement every time, we can store numbers we've already seen in a hash map and check for the complement in constant time.

How It Works

We iterate through the array once. For each element, we calculate its complement (the value needed to reach the target). If the complement already exists in our hash map, we've found our pair. Otherwise, we store the current element's value as a key and its index as the value, then continue.

Implementation

package main

import "fmt"

func twoSum(nums []int, target int) []int {
    // Create a map to store value -> index pairs
    seen := make(map[int]int)

    for i, num := range nums {
        complement := target - num

        // Check if the complement exists in the map
        if j, found := seen[complement]; found {
            return []int{j, i}
        }

        // Store the current number with its index
        seen[num] = i
    }

    return nil
}

func main() {
    nums := []int{2, 7, 11, 15}
    target := 9
    result := twoSum(nums, target)
    fmt.Println(result) // Output: [0 1]

    // Additional test cases
    fmt.Println(twoSum([]int{3, 2, 4}, 6))       // Output: [1 2]
    fmt.Println(twoSum([]int{3, 3}, 6))           // Output: [0 1]
    fmt.Println(twoSum([]int{-1, -2, -3, -4}, -6)) // Output: [1 3]
}

Complexity Analysis

This approach reduces the time complexity to O(n) because we traverse the array only once, and each hash map lookup takes O(1) on average. The space complexity becomes O(n) in the worst case, as we may need to store nearly all elements in the map before finding a match.

Step-by-Step Walkthrough

Let's trace through the example nums = [2, 7, 11, 15] with target = 9:

• Iteration 0: num = 2, complement = 9 - 2 = 7. The map is empty, so 7 is not found. Store seen[2] = 0. Map is now {2: 0}.
• Iteration 1: num = 7, complement = 9 - 7 = 2. Check the map: 2 exists at index 0. Return [0, 1].

The algorithm terminates after just two iterations, demonstrating the efficiency of the hash map approach.

Handling Edge Cases

Real-world inputs can be unpredictable. Here are some edge cases to consider and how the hash map solution handles them:

• Duplicate values: If the array contains duplicates like [3, 3] with target 6, the algorithm works correctly because we check for the complement before adding the current element to the map.
• Negative numbers: The arithmetic works identically with negative numbers since Go handles signed integers natively.
• No solution exists: The function returns nil, which callers should check before using the result.
• Large arrays: The O(n) time complexity ensures the solution scales well even with millions of elements.

Best Practices

Choose the Right Data Structure

Go's built-in map type is ideal for this problem. It provides average O(1) lookup and insertion. Avoid using slices for lookups, as searching a slice is O(n).

Validate Inputs Early

In production code, always validate your inputs. Check for empty arrays, nil slices, and arrays with fewer than two elements before processing.

func twoSumSafe(nums []int, target int) ([]int, error) {
    if nums == nil || len(nums) < 2 {
        return nil, fmt.Errorf("input array must contain at least two elements")
    }

    seen := make(map[int]int)
    for i, num := range nums {
        complement := target - num
        if j, found := seen[complement]; found {
            return []int{j, i}, nil
        }
        seen[num] = i
    }

    return nil, fmt.Errorf("no two sum solution found")
}

Preallocate Maps When Possible

If you know the approximate size of the input, preallocating the map can reduce memory allocations and improve performance. Go's make(map[int]int, size) hint helps the runtime allocate an appropriately sized hash table.

Write Comprehensive Tests

Use Go's built-in testing framework to cover all edge cases:

package main

import "testing"

func TestTwoSum(t *testing.T) {
    tests := []struct {
        name     string
        nums     []int
        target   int
        expected []int
    }{
        {"basic case", []int{2, 7, 11, 15}, 9, []int{0, 1}},
        {"duplicates", []int{3, 3}, 6, []int{0, 1}},
        {"negatives", []int{-1, -2, -3, -4}, -6, []int{1, 3}},
        {"non-adjacent", []int{1, 5, 8, 3, 9}, 11, []int{2, 3}},
    }

    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            result := twoSum(tt.nums, tt.target)
            if result[0] != tt.expected[0] || result[1] != tt.expected[1] {
                t.Errorf("got %v, want %v", result, tt.expected)
            }
        })
    }
}

Benchmark Your Solution

Use Go's benchmarking tools to measure performance and identify bottlenecks:

func BenchmarkTwoSum(b *testing.B) {
    nums := make([]int, 10000)
    for i := range nums {
        nums[i] = i
    }
    target := 19997 // Will match near the end

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        twoSum(nums, target)
    }
}

Common Mistakes to Avoid

• Using the same element twice: Always ensure you're not matching an element with itself. The hash map approach naturally avoids this because we check for the complement before adding the current element.
• Returning values instead of indices: The problem asks for indices, not values. Keep track of positions, not just the numbers.
• Ignoring the no-solution case: Always handle the scenario where no valid pair exists, even if the problem guarantees a solution.
• Modifying the input array: Avoid sorting or modifying the original array, as this would change the indices you need to return.

Conclusion

The Two Sum problem is a perfect introduction to algorithmic problem solving in Go. By progressing from the brute force O(n²) approach to the optimal O(n) hash map solution, you learn how to identify opportunities for optimization through smarter data structure usage. The hash map pattern demonstrated here — storing previously seen values for constant-time lookup — is a versatile technique that applies to countless other problems, from finding duplicates to detecting cycles in data. By following the best practices of input validation, comprehensive testing, and performance benchmarking, you can write Go code that is not only correct but also production-ready. Master this foundational problem, and you'll be well-equipped to tackle more complex algorithmic challenges with confidence.