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.

Analogy: Imagine you have a list of prices and a gift card. You check each price and remember it. When you see a price, you check if the gift card minus that price is something you already saw.

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

We start with empty memory (hash) and look at each number one by one.

Dry Run Walkthrough

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

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

Step 1: Look at first number 2, check if 9 - 2 = 7 is in hash

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

Why: We have no numbers remembered yet, so 7 is not found

Step 2: Add 2 to hash with index 0

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

Why: Remember 2 for future checks

Step 3: Look at second number 7, check if 9 - 7 = 2 is in hash

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

Why: 2 is found in hash, so pair found

Step 4: Return indices 0 and 1

Result: [0, 1]

Why: These two numbers add up to target 9

Result:

Result: [0, 1]

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Simple hash node for storing number and index
typedef struct HashNode {
    int key;
    int val;
    struct HashNode* next;
} HashNode;

// Hash map with chaining
#define HASH_SIZE 100

HashNode* hashMap[HASH_SIZE];

int hash(int key) {
    return abs(key) % HASH_SIZE;
}

void insert(int key, int val) {
    int h = hash(key);
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    node->key = key;
    node->val = val;
    node->next = hashMap[h];
    hashMap[h] = node;
}

int find(int key) {
    int h = hash(key);
    HashNode* curr = hashMap[h];
    while (curr != NULL) {
        if (curr->key == key) return curr->val;
        curr = curr->next;
    }
    return -1;
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    for (int i = 0; i < HASH_SIZE; i++) hashMap[i] = NULL;
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        int foundIndex = find(complement);
        if (foundIndex != -1) {
            int* result = (int*)malloc(2 * sizeof(int));
            result[0] = foundIndex;
            result[1] = i;
            *returnSize = 2;
            return result;
        }
        insert(nums[i], i);
    }
    *returnSize = 0;
    return NULL;
}

int main() {
    int nums[] = {2, 7, 11, 15};
    int target = 9;
    int returnSize = 0;
    int* result = twoSum(nums, 4, target, &returnSize);
    if (result != NULL) {
        printf("[%d, %d]\n", result[0], result[1]);
        free(result);
    } else {
        printf("No solution\n");
    }
    return 0;
}

for (int i = 0; i < numsSize; i++) {

iterate over each number in the array

int complement = target - nums[i];

calculate the number needed to reach target

int foundIndex = find(complement);

check if complement is already in hash

if (foundIndex != -1) {

if complement found, return indices

insert(nums[i], i);

store current number and its index in hash

Output

[0, 1]

Complexity Analysis

Time: O(n) because we check each number once and hash lookups are O(1) on average

Space: O(n) because we store each number in the hash map

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

Edge Cases

Empty array

Returns no solution because no pairs exist

DSA C

if (foundIndex != -1) {

No two numbers add to target

Returns no solution (NULL)

DSA C

if (foundIndex != -1) {

Two identical numbers add to target

Works correctly if both numbers appear and are stored separately

DSA C

insert(nums[i], i);

When to Use This Pattern

When you need to find two numbers that add up to a target quickly, use a hash map to remember seen numbers and check complements in O(1).

Common Mistakes

Mistake: Checking for complement after inserting current number causes wrong answer when complement equals current number
Fix: Check for complement before inserting current number into 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 an array.

Remember numbers seen so far and check if the needed complement exists before adding 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 all pairs of numbers

B. To sort the array before searching

C. To store numbers and their indices for quick lookup

D. To reverse the array elements

Solution

1. Step 1: Understand the role of hash map in Two Sum

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

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 again.

3. Final Answer:

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

4. Quick Check:

   Hash map = quick lookup [OK]

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

Common Mistakes:

• Thinking hash map sorts the array
• Assuming hash map stores all pairs
• Confusing hash map with array reversal

2. Which of the following is the correct syntax to declare a hash map (dictionary) in C for the Two Sum problem?

easy

A. unordered_map hashmap;

B. int hashmap[1000];

C. map hashmap = new map();

D. dict hashmap = {};

Solution

1. Step 1: Identify C++ STL syntax for hash map

   In C++, unordered_map is used for hash maps with integer keys and values.

2. Step 2: Check other options for correctness

   int hashmap[1000]; is a fixed-size array, not a hash map. map hashmap = new map(); is invalid syntax. dict hashmap = {}; is Python syntax.

3. Final Answer:

   unordered_map hashmap; -> Option A

4. Quick Check:

   unordered_map = hash map in C++ [OK]

Hint: Use unordered_map for hash map in C++ [OK]

Common Mistakes:

• Using array instead of hash map
• Confusing Python or Java syntax with C++
• Incorrect map declaration syntax

3. What will be the output of the following code snippet for input nums = [2, 7, 11, 15], target = 9?

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    unordered_map map;
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        if (map.find(complement) != map.end()) {
            int* result = (int*)malloc(2 * sizeof(int));
            result[0] = map[complement];
            result[1] = i;
            *returnSize = 2;
            return result;
        }
        map[nums[i]] = i;
    }
    *returnSize = 0;
    return NULL;
}

medium

A. [1, 0]

B. [0, 1]

C. [2, 3]

D. NULL

Solution

1. Step 1: Trace the loop and hash map insertions

   At i=0, map = {2:0}. At i=1, complement = 9-7=2 found in map at index 0.

2. Step 2: Return indices of complement and current number

   Return [0,1] as the pair that sums to 9.

3. Final Answer:

   [0, 1] -> Option B

4. Quick Check:

   nums[0]+nums[1] = 2+7 = 9 [OK]

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

Common Mistakes:

• Returning indices in wrong order
• Not checking complement before insertion
• Returning NULL when pair exists

4. Identify the bug in this Two Sum hash map solution snippet:

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

medium

A. Loop should start from i = 1

B. map should store complement instead of current number

C. Return statement syntax is invalid in C

D. Complement check should happen before inserting current number

Solution

1. Step 1: Analyze order of operations in loop

   Current number is inserted before checking complement, causing false positive when complement equals current number.

2. Step 2: Correct order to check complement before insertion

   Check if complement exists in map first, then insert current number to avoid matching with itself.

3. Final Answer:

   Complement check should happen before inserting current number -> Option D

4. Quick Check:

   Check complement before insert [OK]

Hint: Check complement before adding current number to map [OK]

Common Mistakes:

• Inserting before checking complement
• Wrong return syntax in C
• Starting loop from wrong index

5. Given an array nums = [3, 3, 4, 5] and target = 6, what will the Two Sum hash map solution return and why?

hard

A. [0, 1] because nums[0] + nums[1] = 3 + 3 = 6

B. [2, 3] because nums[2] + nums[3] = 4 + 5 = 9

C. NULL because no two numbers sum to 6

D. [1, 0] because indices order is reversed

Solution

1. Step 1: Trace the hash map insertions and complement checks

   At i=0, map = {3:0}. At i=1, complement = 6-3=3 found at index 0.

2. Step 2: Return indices of the first valid pair

   Return [0,1] as the pair that sums to 6.

3. Final Answer:

   [0, 1] because nums[0] + nums[1] = 3 + 3 = 6 -> Option A

4. Quick Check:

   3 + 3 = 6 [OK]

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

Common Mistakes:

• Ignoring duplicate values
• Returning wrong indices order
• Assuming no pair exists when duplicates present