Subarray Sum Equals K Using Hash Map in DSA C - Time & Space Complexity

Time Complexity: Subarray Sum Equals K Using Hash Map

O(n)

Understanding Time Complexity

We want to know how fast the algorithm finds subarrays that add up to a target sum.

How does the time needed grow as the input array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int subarraySum(int* nums, int numsSize, int k) {
    int count = 0, sum = 0;
    int map[20001] = {0}; // hash map for prefix sums
    map[10000] = 1; // offset for zero sum
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
        count += map[sum - k + 10000];
        map[sum + 10000]++;
    }
    return count;
}
    

This code counts how many continuous parts of the array add up exactly to k using a hash map for prefix sums.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single loop through the array once.
• How many times: Exactly once for each element (n times).

How Execution Grows With Input

Each new element adds a fixed amount of work: updating sums and hash map counts.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The work grows directly in proportion to the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find subarrays grows linearly as the array gets bigger.

Common Mistake

[X] Wrong: "Because we check sums inside a loop, it must be O(n²)."

[OK] Correct: The hash map lets us find needed sums instantly, so no nested loops are needed.

Interview Connect

Understanding this linear-time approach shows you can use clever data structures to speed up problems that seem slow at first.

Self-Check

"What if we used a nested loop to check all subarrays instead of a hash map? How would the time complexity change?"