Two Sum Problem Classic Hash Solution in DSA C++

Mental Model

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

Analogy: Imagine shopping with a list of prices and a budget. You check each price and ask: 'Have I seen a price that pairs with this to reach my budget?' If yes, you found your pair.

nums: [2, 7, 11, 15]
hash: {}
↑ current index at 0

Dry Run Walkthrough

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

Goal: Find indices of two numbers that add up to 9

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

hash: {} -> no 7 found
nums: [2, 7, 11, 15]
↑ at index 0

Why: We need to see if the complement (7) was seen before to form 9

Step 2: Add 2 with index 0 to hash

hash: {2:0}
nums: [2, 7, 11, 15]
↑ at index 1

Why: Store 2 so future numbers can check if they pair with it

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

hash: {2:0} -> 2 found at index 0
nums: [2, 7, 11, 15]
↑ at index 1

Why: Found complement 2, so 2 + 7 = 9

Step 4: Return indices [0, 1]

Result: [0, 1]

Why: These indices point to numbers that sum to target

Result:

hash: {2:0, 7:1}
nums: [2, 7, 11, 15]
Result: indices [0, 1]

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> twoSum(const vector<int>& nums, int target) {
        unordered_map<int, int> hashMap; // number -> index
        for (int i = 0; i < (int)nums.size(); ++i) {
            int complement = target - nums[i];
            if (hashMap.find(complement) != hashMap.end()) {
                return {hashMap[complement], i}; // found pair
            }
            hashMap[nums[i]] = i; // store current number
        }
        return {}; // no pair found
    }
};

int main() {
    Solution sol;
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    vector<int> result = sol.twoSum(nums, target);
    if (!result.empty()) {
        cout << result[0] << " " << result[1] << "\n";
    } else {
        cout << "No pair found\n";
    }
    return 0;
}

for (int i = 0; i < (int)nums.size(); ++i) {

iterate over each number to check for complement

int complement = target - nums[i];

calculate the number needed to reach target with current number

if (hashMap.find(complement) != hashMap.end()) {

check if complement was seen before

return {hashMap[complement], i};

return indices of the two numbers that sum to target

hashMap[nums[i]] = i;

store current number and its index for future complement checks

Output

0 1

Complexity Analysis

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

Space: O(n) because we store up to n numbers in the hash map

vs Alternative: Compared to a double loop O(n^2) approach, this hash method is much faster by trading space for time

Edge Cases

empty array

returns empty result since no pairs exist

DSA C++

return {}; // no pair found

no two numbers sum to target

returns empty result after full scan

DSA C++

return {}; // no pair found

multiple pairs possible

returns first valid pair found

DSA C++

return {hashMap[complement], i};

When to Use This Pattern

When asked to find two elements summing 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 inserting current number into hash map
Fix: Check for complement before inserting current number to avoid pairing number with itself

Mistake: Using nested loops instead of hash map causing slow O(n^2) time
Fix: Use hash map to achieve O(n) time by single pass lookup

Summary

Find two indices whose numbers add up to the target using a hash map for quick lookup.

Use when you need to find pairs summing to a target efficiently in one pass.

The key insight is to check if the complement exists before storing the current number.

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