Two Sum Problem Classic Hash Solution in DSA C - Time & Space Complexity

Time Complexity: Two Sum Problem Classic Hash Solution

O(n)

Understanding Time Complexity

We want to know how the time needed to find two numbers that add up to a target grows as the list gets bigger.

How does the solution's speed change when the input size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int* map = (int*)calloc(2048, sizeof(int));
    int* result = (int*)malloc(2 * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        if (map[complement & 2047]) {
            result[0] = map[complement & 2047] - 1;
            result[1] = i;
            *returnSize = 2;
            free(map);
            return result;
        }
        map[nums[i] & 2047] = i + 1;
    }
    *returnSize = 0;
    free(map);
    return NULL;
}

This code finds two numbers in an array that add up to a target using a simple hash map for quick lookups.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop through the array once.
• How many times: Exactly once for each element in the input array.

How Execution Grows With Input

Each new number is checked and stored once, so the work grows steadily as the list grows.

Input Size (n)	Approx. Operations
10	About 10 checks and inserts
100	About 100 checks and inserts
1000	About 1000 checks and inserts

Pattern observation: The number of operations grows directly with input size, doubling input roughly doubles work.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the two numbers grows in a straight line with the size of the input list.

Common Mistake

[X] Wrong: "The hash map lookup inside the loop makes this solution slower than a simple double loop."

[OK] Correct: Hash map lookups are very fast and happen in constant time, so the overall time stays linear, unlike the double loop which grows much faster.

Interview Connect

Understanding this solution's time complexity shows you can use smart data structures to speed up searching, a key skill in many coding challenges.

Self-Check

"What if we used a sorted array and binary search instead of a hash map? How would the time complexity change?"