Two Sum Problem Classic Hash Solution in DSA Go - Build from Scratch

Two Sum Problem Classic Hash Solution

📖 Scenario: You are helping a cashier find two items in a list that add up to a customer's gift card amount. The cashier wants to quickly find the pair of item prices that match the gift card value.

🎯 Goal: Build a Go program that finds two numbers in a list that add up to a target sum using a hash map for fast lookup.

📋 What You'll Learn

Create a slice of integers called nums with the values 2, 7, 11, 15

Create an integer variable called target and set it to 9

Use a map called numMap to store numbers and their indices

Write a for loop with index i and value num to iterate over nums

Inside the loop, check if target - num exists in numMap

If found, print the indices as a slice in the format [index1 index2]

💡 Why This Matters

🌍 Real World

Finding pairs of items that sum to a specific value is useful in shopping apps, budgeting tools, and financial software.

💼 Career

This problem teaches hash map usage and efficient searching, which are common in software engineering interviews and real-world coding tasks.

1

Create the list of numbers

Create a slice of integers called nums with the values 2, 7, 11, and 15.

DSA Go

package main

func main() {
    // Create the slice nums with values 2, 7, 11, 15
    // Your code here
}

Hint

Use nums := []int{2, 7, 11, 15} to create the slice.

2

Set the target sum

Create an integer variable called target and set it to 9.

DSA Go

package main

import "fmt"

func main() {
    nums := []int{2, 7, 11, 15}
    // Create the target variable and set it to 9
    // Your code here
}

Hint

Use target := 9 to create the target variable.

3

Find two numbers that add up to target using a map

Create a map called numMap to store integers as keys and their indices as values. Use a for loop with variables i and num to iterate over nums. Inside the loop, check if target - num exists in numMap. If it exists, print the indices as a slice in the format [index1 index2] and return. Otherwise, add num and its index i to numMap.

DSA Go

package main

import "fmt"

func main() {
    nums := []int{2, 7, 11, 15}
    target := 9
    // Create numMap and write the for loop to find two sum
    // Your code here
}

Hint

Use a map to store numbers and their indices. Check if the complement exists in the map inside the loop.

4

Print the result

Print the indices of the two numbers that add up to target as a slice in the format [index1 index2]. This should already be done inside the loop with fmt.Println([]int{j, i}). Run the program to see the output.

DSA Go

package main

import "fmt"

func main() {
    nums := []int{2, 7, 11, 15}
    target := 9
    numMap := make(map[int]int)
    for i, num := range nums {
        complement := target - num
        if j, found := numMap[complement]; found {
            // Print the indices here
            // Your code here
            return
        }
        numMap[num] = i
    }
}

Hint

The output should be the indices of the two numbers that add up to 9, which are 0 and 1.

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