Two Sum Problem Classic Hash Solution in DSA C++ - Deep Dive

Overview - Two Sum Problem Classic Hash Solution

What is it?

The Two Sum problem asks us to find two numbers in a list that add up to a specific target number. We want to return the positions of these two numbers. The classic hash solution uses a fast lookup method to find the pair quickly without checking every combination. This makes the problem easier and faster to solve.

Why it matters

Without an efficient way to find pairs that add up to a target, we would have to check every possible pair, which takes a long time for big lists. This slow method can make programs lag or fail when handling large data. The hash solution speeds this up, making apps and systems that rely on quick searches work smoothly.

Where it fits

Before this, you should understand arrays (lists) and basic loops. After this, you can learn about hash maps/dictionaries in more depth and explore other search and optimization problems like Three Sum or Subarray Sum.

Mental Model

Core Idea

Use a fast lookup table to remember numbers seen so far and check if the complement to the target exists instantly.

Think of it like...

Imagine you are at a party and want to find a friend who has a matching puzzle piece to complete your puzzle. Instead of asking everyone one by one, you keep a list of pieces you have and quickly check if someone has the piece you need when you meet them.

Input array: [2, 7, 11, 15]
Target: 9

Step-by-step:
Index 0: number=2, need 7 (9-2)
Hash map: {}
Add 2 with index 0

Index 1: number=7, need 2 (9-7)
Hash map: {2:0}
2 found in map! Return [0,1]

Result: 0 -> 1 -> null

Build-Up - 7 Steps

1

Foundation

Understanding the Two Sum Problem

Concept: Learn what the problem asks: find two numbers that add up to a target and return their positions.

Given an array of numbers and a target number, find two different numbers in the array that add up exactly to the target. Return their indices (positions). For example, in [2, 7, 11, 15] with target 9, 2 and 7 add up to 9, so return their indices [0, 1].

Result

Clear understanding of the problem and expected output format.

Knowing exactly what the problem wants helps avoid confusion and guides the solution approach.

2

Foundation

Brute Force Approach Basics

Concept: Try every pair of numbers to see if they add up to the target.

Use two loops: the outer loop picks one number, the inner loop checks every other number to see if their sum equals the target. This works but is slow for big lists because it checks many pairs.

Result

For input [2,7,11,15] and target 9, loops find pair (2,7) at indices (0,1).

Understanding brute force shows why we need a faster method for large inputs.

3

Intermediate

Introducing Hash Map for Fast Lookup

Concept: Use a hash map (dictionary) to remember numbers and their indices for quick searching.

As you go through the list, calculate the number needed to reach the target (target - current number). Check if this needed number is already in the hash map. If yes, return the pair of indices. If no, add the current number and its index to the map.

Result

For input [2,7,11,15] and target 9, at index 1, find 7 needs 2, which is in map at index 0, so return [0,1].

Using a hash map reduces the search time from checking all pairs to just one pass through the list.

4

Intermediate

Implementing the Classic Hash Solution in C++

🤔Before reading on: do you think the hash map stores numbers as keys or indices as keys? Commit to your answer.

Concept: Write the code that uses a hash map to solve the problem efficiently in one pass.

#include #include #include std::vector twoSum(const std::vector& nums, int target) { std::unordered_map num_map; // number -> index for (int i = 0; i < nums.size(); ++i) { int complement = target - nums[i]; if (num_map.find(complement) != num_map.end()) { return {num_map[complement], i}; } num_map[nums[i]] = i; } return {}; // no solution found } int main() { std::vector nums = {2, 7, 11, 15}; int target = 9; std::vector result = twoSum(nums, target); std::cout << result[0] << " -> " << result[1] << " -> null" << std::endl; return 0; }

Result

Output: 0 -> 1 -> null

Knowing the hash map stores numbers as keys and indices as values is key to quick complement lookup.

5

Intermediate

Handling Edge Cases and No Solution

🤔Before reading on: do you think the code returns indices if no pair sums to target or returns empty? Commit your guess.

Concept: Learn how the solution behaves when no valid pair exists and how to handle that gracefully.

If no two numbers add up to the target, the function returns an empty vector. This means no solution was found. It's important to check for this case in real programs to avoid errors.

Result

For input [1,2,3] and target 7, output is empty (no indices).

Handling no-solution cases prevents crashes and makes the code robust.

6

Advanced

Time and Space Complexity Analysis

🤔Before reading on: do you think the hash solution is O(n) time or O(n^2)? Commit your answer.

Concept: Understand how fast and memory-heavy the hash solution is compared to brute force.

The hash solution goes through the list once, so time complexity is O(n). Each lookup and insert in the hash map is O(1) on average. Space complexity is O(n) because we store numbers and indices in the map.

Result

The solution is much faster than brute force for large inputs but uses extra memory.

Knowing complexity helps choose the right solution for different constraints.

7

Expert

Subtle Behavior with Duplicate Numbers

🤔Before reading on: if the input has duplicates, does the solution always return the first valid pair or can it return others? Commit your answer.

Concept: Explore how the hash map solution handles duplicates and which pair it returns.

The hash map updates the index for a number if it appears again. This means the solution returns the pair involving the latest occurrence of a number. For example, in [3,3,4] with target 6, it returns indices [0,1]. But if the input is [3,4,3], it returns [0,2]. This subtlety can affect which pair is found first.

Result

The solution returns one valid pair but not necessarily the first pair in order of appearance.

Understanding this behavior helps when the problem requires the earliest pair or all pairs.

Under the Hood

The hash map stores each number as a key and its index as the value. When processing a number, the algorithm calculates the complement needed to reach the target. It then checks if this complement is already in the map. If yes, it immediately returns the stored index and current index. This avoids nested loops by trading time for space.

Why designed this way?

This approach was designed to reduce the time complexity from O(n^2) to O(n) by using extra memory. Hash maps provide average constant time lookup, making them ideal for this problem. Alternatives like sorting and two pointers require sorted input and lose original indices, so the hash map preserves order and indices.

┌───────────────┐
│ Input Array   │
│ [2, 7, 11, 15]│
└──────┬────────┘
       │
       ▼
┌─────────────────────────────┐
│ Loop over each number i      │
│   complement = target - nums[i] │
│   Check if complement in map │
│     Yes -> return indices    │
│     No -> add nums[i]:i to map│
└─────────────┬───────────────┘
              │
              ▼
       ┌─────────────┐
       │ Result Pair │
       │ [index1, i] │
       └─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does the hash map store indices as keys and numbers as values? Commit yes or no.

Common Belief: The hash map stores indices as keys and numbers as values.

Reality: The hash map stores numbers as keys and their indices as values.

Why it matters: If reversed, lookup for complements becomes impossible or inefficient, breaking the solution.

Quick: Is the hash solution always faster than sorting and two pointers? Commit yes or no.

Common Belief: The hash solution is always the fastest way to solve Two Sum.

Reality: While hash solution is O(n), sorting and two pointers is O(n log n) but uses less space and can be faster in practice for some inputs.

Why it matters: Choosing the wrong method can waste memory or be slower depending on input size and constraints.

Quick: Does the hash solution find all pairs that sum to target? Commit yes or no.

Common Belief: The hash solution finds all pairs that add up to the target.

Reality: The classic hash solution returns only one valid pair and stops.

Why it matters: Assuming it finds all pairs can cause bugs if multiple pairs are needed.

Quick: Can the hash solution handle inputs with negative numbers? Commit yes or no.

Common Belief: The hash solution only works with positive numbers.

Reality: It works with any integers, positive or negative.

Why it matters: Limiting to positive numbers restricts use cases unnecessarily.

Expert Zone

1

The hash map updates the index for duplicate numbers, affecting which pair is returned.

2

Hash collisions in the map are handled internally but can affect performance in rare cases.

3

The solution assumes exactly one valid pair exists; handling multiple or no pairs requires modifications.

When NOT to use

Avoid this approach when memory is very limited or when the input is already sorted and you want to save space; in such cases, use the two-pointer technique after sorting. Also, if you need all pairs, this method needs extension or a different approach.

Production Patterns

Used in real-time systems where quick pair matching is needed, such as fraud detection (matching transactions), gaming (matching scores), or recommendation engines (matching preferences). Often combined with streaming data structures for continuous input.

Connections

Hash Map / Dictionary

Builds-on

Understanding hash maps deeply improves grasp of the Two Sum solution and many other fast lookup problems.

Two Pointer Technique

Alternative approach

Knowing two pointers helps choose the best method depending on input sorting and memory constraints.

Real-time Inventory Matching (Supply Chain)

Same pattern

Matching pairs in Two Sum is like matching supply and demand items quickly in logistics, showing how algorithms apply beyond coding.

Common Pitfalls

#1 Using nested loops for large inputs causes slow performance.

Wrong approach:

for (int i = 0; i < nums.size(); ++i) {
for (int j = i + 1; j < nums.size(); ++j) {
if (nums[i] + nums[j] == target) return {i, j};
}
}

Correct approach:

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

Root cause:

Not knowing how to use hash maps for fast lookup leads to inefficient brute force.

#2 Checking for complement after inserting current number causes wrong results with duplicates.

Wrong approach:

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

Correct approach:

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

Root cause:

Inserting before checking causes the current number to match itself incorrectly.

#3 Not handling no solution case leads to runtime errors.

Wrong approach:

auto result = twoSum(nums, target);
std::cout << result[0] << " " << result[1] << std::endl; // no check

Correct approach:

auto result = twoSum(nums, target);
if (!result.empty()) {
std::cout << result[0] << " " << result[1] << std::endl;
} else {
std::cout << "No valid pair found" << std::endl;
}

Root cause:

Assuming a solution always exists without checking causes crashes.

Key Takeaways

The Two Sum problem finds two numbers that add up to a target and returns their indices.

Using a hash map allows checking complements in constant time, reducing overall time to linear.

The hash map stores numbers as keys and their indices as values for quick lookup.

Handling edge cases like duplicates and no solution is important for robust code.

Understanding time and space trade-offs helps choose the best solution for different scenarios.

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