Two Sum Problem Classic Hash Solution in DSA Go

Mental Model

We want to find two numbers that add up to a target by remembering numbers we've seen before.

Analogy: Imagine you have a list of prices and a gift card. You check each price and remember it. When you see a price that matches what you need to reach the gift card amount, you find your pair.

nums: [2] [7] [11] [15]
          ↑
hash: {}

Dry Run Walkthrough

Input: nums: [2, 7, 11, 15], target: 9

Goal: Find two indices where the numbers add up to 9

Step 1: Check number 2 at index 0, look for 9 - 2 = 7 in hash

nums: [2] [7] [11] [15]
          ↑
hash: {}

Why: We want to see if the complement 7 is already seen

Step 2: 7 not found in hash, add 2 with index 0 to hash

nums: [2] [7] [11] [15]
             ↑
hash: {2:0}

Why: Remember 2 for future matches

Step 3: Check number 7 at index 1, look for 9 - 7 = 2 in hash

nums: [2] [7] [11] [15]
                ↑
hash: {2:0}

Why: Check if complement 2 is in hash to form target

Step 4: 2 found in hash at index 0, return indices [0,1]

nums: [2] [7] [11] [15]
                ↑
hash: {2:0}

Why: Found the pair that sums to target

Result:

nums: [2] [7] [11] [15]
Indices: [0, 1]

Annotated Code

DSA Go

package main

import "fmt"

func twoSum(nums []int, target int) []int {
    hash := make(map[int]int) // number to index
    for i, num := range nums {
        complement := target - num
        if idx, found := hash[complement]; found {
            return []int{idx, i} // found pair
        }
        hash[num] = i // store current number
    }
    return []int{} // no pair found
}

func main() {
    nums := []int{2, 7, 11, 15}
    target := 9
    result := twoSum(nums, target)
    fmt.Printf("Indices: [%d, %d]\n", result[0], result[1])
}

for i, num := range nums {

iterate over each number with its index

complement := target - num

calculate the number needed to reach target

if idx, found := hash[complement]; found {

check if complement was seen before

return []int{idx, i} // found pair

return indices of the two numbers that sum to target

hash[num] = i // store current number

remember current number and its index for future checks

Output

Indices: [0, 1]

Complexity Analysis

Time: O(n) because we scan the list once and do constant time lookups in the hash map

Space: O(n) because in the worst case we store all numbers in the hash map

vs Alternative: Compared to checking all pairs (O(n^2)), this hash solution is much faster by using extra space

Edge Cases

empty list

returns empty result since no pairs exist

DSA Go

return []int{} // no pair found

no two numbers sum to target

returns empty result after full scan

DSA Go

return []int{} // no pair found

multiple pairs possible

returns the first pair found during iteration

DSA Go

return []int{idx, i} // found pair

When to Use This Pattern

When you need to find two elements that sum to a target quickly, use a hash map to remember seen numbers and check complements in one pass.

Common Mistakes

Mistake: Checking for complement after adding current number to hash causes missing pairs
Fix: Check for complement before adding current number to hash

Summary

Find two indices of numbers that add up to a target using a hash map.

Use when you want a fast solution to find pairs summing to a target in one pass.

Remember to check for the complement before storing the current number to avoid missing pairs.

Practice

1. What is the main idea behind the Two Sum Problem Classic Hash Solution?

easy

A. Use a hash map to store numbers and their indices for quick lookup

B. Sort the array and use two pointers to find the sum

C. Use nested loops to check every pair of numbers

D. Use recursion to find pairs that add up to the target

Solution

1. Step 1: Understand the problem goal

   The goal is to find two numbers in the array that add up to a target value.

2. Step 2: Use a hash map for efficient lookup

   By storing each number and its index in a hash map, we can check if the complement (target - current number) exists quickly.

3. Final Answer:

   Use a hash map to store numbers and their indices for quick lookup -> Option A

4. Quick Check:

   Hash map lookup = fast pair finding [OK]

Hint: Use a hash map to find complements quickly [OK]

Common Mistakes:

• Trying to use nested loops which is slower
• Sorting the array which is unnecessary here
• Not storing indices with numbers

2. Which of the following Go code snippets correctly initializes a hash map to store integers as keys and values?

easy

A. var m map[int]int

B. m := map[int]int

C. m := make(map[int]int)

D. m := map[int]int(make())

Solution

1. Step 1: Recall Go map initialization syntax

   Maps in Go are initialized using the built-in make function like make(map[keyType]valueType).

2. Step 2: Identify correct syntax

   m := make(map[int]int) uses make(map[int]int) which is the correct way to create an empty map with int keys and int values.

3. Final Answer:

   m := make(map[int]int) -> Option C

4. Quick Check:

   make(map[int]int) = correct map init [OK]

Hint: Use make(map[key]value) to create maps in Go [OK]

Common Mistakes:

• Using var without make causes nil map
• Incorrect syntax like map[int]int(make())
• Using empty braces without make in some contexts

3. What will be the output of the following Go code snippet?

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i, num := range nums {
        if j, ok := m[target-num]; ok {
            return []int{j, i}
        }
        m[num] = i
    }
    return nil
}

fmt.Println(twoSum([]int{2, 7, 11, 15}, 9))

medium

A. [1 0]

B. [0 1]

C. [2 3]

D. nil

Solution

1. Step 1: Trace the loop and map updates

   At i=0, num=2, map is empty, so store m[2]=0.
   At i=1, num=7, check if m[9-7=2] exists, yes at index 0.
   Return [0,1].

2. Step 2: Confirm returned indices

   The function returns indices of numbers 2 and 7 which sum to 9, so output is [0 1].

3. Final Answer:

   [0 1] -> Option B

4. Quick Check:

   Indices of 2 and 7 = [0 1] [OK]

Hint: Check map for complement before inserting current number [OK]

Common Mistakes:

• Returning indices in wrong order
• Not checking map before insertion
• Returning nil when pair exists

4. Identify the error in the following Go code for the Two Sum problem:

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i, num := range nums {
        if j, ok := m[num-target]; ok {
            return []int{j, i}
        }
        m[num] = i
    }
    return nil
}

medium

A. The complement calculation should be target - num, not num - target

B. The map should store num + target as key

C. The map initialization is incorrect

D. The return statement should return nil earlier

Solution

1. Step 1: Analyze complement calculation

   The complement to find is target - current number, not num - target, because we want a number that adds with num to target.

2. Step 2: Identify the fix

   Change m[num-target] to m[target-num] to correctly check for the complement in the map.

3. Final Answer:

   The complement calculation should be target - num, not num - target -> Option A

4. Quick Check:

   Complement = target - num [OK]

Hint: Complement = target minus current number [OK]

Common Mistakes:

• Swapping target and num in complement
• Incorrect map initialization
• Returning nil too early

5. Given the input array nums = [3, 3, 4, 2] and target 6, what will the Two Sum Classic Hash Solution return?
Consider the code below:

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i, num := range nums {
        if j, ok := m[target-num]; ok {
            return []int{j, i}
        }
        m[num] = i
    }
    return nil
}

medium

A. nil

B. [1 2]

C. [2 3]

D. [0 1]

Solution

1. Step 1: Trace the loop with given input

   i=0, num=3, map empty, store m[3]=0.
   i=1, num=3, check m[6-3=3], found at index 0, return [0,1].

2. Step 2: Confirm returned indices

   Indices 0 and 1 correspond to values 3 and 3 which sum to 6, so output is [0 1].

3. Final Answer:

   [0 1] -> Option D

4. Quick Check:

   3 + 3 = 6 at indices [0 1] [OK]

Hint: Check map for complement before inserting current number [OK]

Common Mistakes:

• Assuming different pairs without checking map
• Returning nil when pair exists
• Confusing indices order