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.