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

Two Sum Problem Classic Hash Solution

📖 Scenario: You are working on a shopping app. You want to find two items whose prices add up to a gift card value.

🎯 Goal: Build a 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 vector of integers called nums with the exact values: 2, 7, 11, 15

Create an integer variable called target and set it to 9

Use an unordered_map called hash_map to store numbers and their indices

Use a for loop with variable i to iterate over nums

Inside the loop, check if target - nums[i] exists in hash_map

If found, store the indices in a vector called result

Print the two indices stored in result

💡 Why This Matters

🌍 Real World

Finding two items in a list that sum to a gift card value is common in shopping apps and budgeting tools.

💼 Career

This problem teaches hash map usage and efficient searching, which are key skills for software developers working on performance-critical applications.

1

Create the list of numbers

Create a vector of integers called nums with these exact values: 2, 7, 11, 15

DSA C++

#include 
#include 
#include 

int main() {

    // Create vector nums with values 2, 7, 11, 15
    // Your code here

    return 0;
}

Hint

Use std::vector<int> and initialize it with the values inside curly braces.

2

Set the target sum

Create an integer variable called target and set it to 9

DSA C++

#include 
#include 
#include 

int main() {
    std::vector nums = {2, 7, 11, 15};

    // Create int variable target and set to 9
    // Your code here

    return 0;
}

Hint

Use int target = 9; to create the variable.

3

Find two indices using hash map

Create an unordered_map called hash_map to store numbers and their indices. Use a for loop with variable i to iterate over nums. Inside the loop, check if target - nums[i] exists in hash_map. If found, create a vector called result with the two indices and break the loop. Otherwise, add nums[i] and i to hash_map.

DSA C++

#include 
#include 
#include 

int main() {
    std::vector nums = {2, 7, 11, 15};
    int target = 9;

    // Create unordered_map hash_map
    // Use for loop with i to iterate nums
    // Check if target - nums[i] in hash_map
    // If found, create vector result with indices and break
    // Else add nums[i] and i to hash_map
    // Your code here

    return 0;
}

Hint

Use hash_map.find() to check existence. Store indices in result vector.

4

Print the result indices

Print the two indices stored in the vector result separated by a space.

DSA C++

#include 
#include 
#include 

int main() {
    std::vector nums = {2, 7, 11, 15};
    int target = 9;
    std::unordered_map hash_map;
    std::vector result;

    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (hash_map.find(complement) != hash_map.end()) {
            result = {hash_map[complement], i};
            break;
        }
        hash_map[nums[i]] = i;
    }

    // Print the two indices in result separated by space
    // Your code here

    return 0;
}

Hint

Use std::cout to print result[0] and result[1] separated by a space.

Practice

1. What is the main purpose of using a hash map in the classic Two Sum problem solution?

easy

A. To store numbers and their indices for quick lookup

B. To sort the array before searching

C. To store the sum of all pairs

D. To reverse the array elements

Solution

1. Step 1: Understand the role of hash map

   The hash map stores each number as a key and its index as the value for quick access.

2. Step 2: Explain why quick lookup is needed

   Quick lookup helps find if the complement (target - current number) exists without scanning the entire array.

3. Final Answer:

   To store numbers and their indices for quick lookup -> Option A

4. Quick Check:

   Hash map = quick index lookup [OK]

Hint: Hash map stores values for instant complement search [OK]

Common Mistakes:

• Thinking hash map sorts the array
• Confusing hash map with storing sums
• Assuming hash map reverses elements

2. Which of the following C++ code snippets correctly declares the hash map used in the Two Sum problem to store integer keys and values?

easy

A. std::map<int> map;

B. std::unordered_map map;

C. std::unordered_map<int> map;

D. std::vector map;

Solution

1. Step 1: Identify correct hash map syntax

   std::unordered_map declares a hash map with int keys and int values.

2. Step 2: Explain why others are incorrect

   std::map<int> lacks value type; std::unordered_map<int> lacks value type; std::vector is invalid syntax.

3. Final Answer:

   std::unordered_map<int, int> map; -> Option B

4. Quick Check:

   Correct hash map syntax = std::unordered_map<int, int> [OK]

Hint: Use std::unordered_map<key, value> for hash maps in C++ [OK]

Common Mistakes:

• Omitting value type in map declaration
• Using std::vector instead of map
• Confusing std::map and std::unordered_map syntax

3. What will be the output of the following C++ code snippet for the input array nums = {2, 7, 11, 15} and target = 9?

std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (map.find(complement) != map.end()) {
            return {map[complement], i};
        }
        map[nums[i]] = i;
    }
    return {};
}

int main() {
    auto result = twoSum({2, 7, 11, 15}, 9);
    for (int i : result) std::cout << i << " ";
}

medium

A. [1 0]

B. [2 3]

C. [0 1]

D. No output

Solution

1. Step 1: Trace the loop and map updates

   At i=0, map is empty, insert (2,0). At i=1, complement=9-7=2 found in map at index 0.

2. Step 2: Return indices of complement and current

   Return {0,1} which prints as "0 1".

3. Final Answer:

   [0 1] -> Option C

4. Quick Check:

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

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

Common Mistakes:

• Returning indices in wrong order
• Not checking complement before insertion
• Confusing values with indices

4. Identify the bug in this Two Sum function and select the fix:

std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (map.find(complement) != map.end()) {
            return {i, map[complement]};
        }
        map[nums[i]] = i;
    }
    return {};
}

medium

A. Swap the return indices to {map[complement], i}

B. Change unordered_map to map

C. Insert nums[i] into map before checking complement

D. Return empty vector immediately

Solution

1. Step 1: Analyze the return statement order

   The function returns {i, map[complement]} but correct order is {map[complement], i} to match indices.

2. Step 2: Explain why swapping fixes the bug

   Swapping ensures the first index is of complement and second is current index, matching problem requirement.

3. Final Answer:

   Swap the return indices to {map[complement], i} -> Option A

4. Quick Check:

   Correct index order = complement index, current index [OK]

Hint: Return complement index first, then current index [OK]

Common Mistakes:

• Returning indices in wrong order
• Inserting before checking complement
• Changing map type unnecessarily

5. Given the input array nums = {3, 3, 4, 5} and target = 6, what will the classic Two Sum hash solution return and why?

std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (map.find(complement) != map.end()) {
            return {map[complement], i};
        }
        map[nums[i]] = i;
    }
    return {};
}

hard

A. Empty vector because no two numbers sum to 6

B. [2 3] because 4 and 5 sum to 9, not 6

C. [1 0] because indices are reversed

D. [0 1] because first 3 and second 3 sum to 6

Solution

1. Step 1: Trace the loop with duplicates

   At i=0, map empty, insert (3,0). At i=1, complement=6-3=3 found at index 0.

2. Step 2: Return indices of first and second 3

   Return {0,1} because nums[0] + nums[1] = 3 + 3 = 6.

3. Final Answer:

   [0 1] because first 3 and second 3 sum to 6 -> Option D

4. Quick Check:

   Duplicates allowed, indices 0 and 1 sum to target [OK]

Hint: Duplicates can form valid pairs if sum matches target [OK]

Common Mistakes:

• Ignoring duplicates in map
• Assuming no pair sums to target
• Returning indices in wrong order