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?"

Practice

1. What is the main purpose of using a hash map in the Subarray Sum Equals K problem?

easy

A. To store the original array elements as keys

B. To sort the array elements before processing

C. To keep track of the maximum subarray length

D. To store cumulative sums and their frequencies for quick lookup

Solution

1. Step 1: Understand the problem requirement

   The problem requires finding subarrays whose sums equal a target value k.

2. Step 2: Role of hash map in the solution

   The hash map stores cumulative sums seen so far and their counts to quickly check if a subarray sum equals k exists.

3. Final Answer:

   To store cumulative sums and their frequencies for quick lookup -> Option D

4. Quick Check:

   Hash map stores sums for fast subarray sum checks [OK]

Hint: Hash map tracks sums to find subarrays fast [OK]

Common Mistakes:

• Thinking hash map sorts elements
• Using hash map to store array elements directly
• Confusing hash map with array for indexing

2. Which of the following is the correct way to initialize a hash map in C for storing integer keys and values?

easy

A. map map;

B. HashMap map = new HashMap<>();

C. int map[1000] = {0};

D. unordered_map map;

Solution

1. Step 1: Identify C language syntax

   In C, hash maps are not built-in; arrays can be used as simple maps for small ranges.

2. Step 2: Check options for C syntax

   int map[1000] = {0}; uses an integer array initialized to zero, suitable as a simple map in C.

3. Final Answer:

   int map[1000] = {0}; -> Option C

4. Quick Check:

   Array initialization is valid C syntax [OK]

Hint: Use arrays for maps in C, no built-in hash map [OK]

Common Mistakes:

• Using C++ or Java syntax in C code
• Trying to declare hash maps directly in C
• Not initializing arrays before use

3. What will be the output of the following code snippet in C that counts subarrays summing to k=5?

int arr[] = {1, 2, 3, 2, 1};
int k = 5;
// Assume correct hash map logic implemented
int result = subarraySum(arr, 5, k);
printf("%d", result);

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Identify subarrays summing to 5

   Subarrays: [2,3] (indices 1-2), [3,2] (indices 2-3), [2,3] (indices 3-4); total 3 subarrays.

2. Step 2: Count valid subarrays

   Counting carefully, the subarrays summing to 5 are three in total.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count of subarrays with sum 5 = 3 [OK]

Hint: Count all subarrays with sum k using prefix sums [OK]

Common Mistakes:

• Counting only non-overlapping subarrays
• Missing subarrays starting at index 0
• Incorrectly summing elements

4. Identify the bug in this C code snippet for counting subarrays with sum k using a hash map:

int subarraySum(int* nums, int numsSize, int k) {
    int count = 0, sum = 0;
    int map[10000] = {0};
    map[0] = 1;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
        if (map[sum - k])
            count += map[sum - k];
        map[sum]++;
    }
    return count;
}

medium

A. Array map size is too small for negative sums

B. Missing initialization of count variable

C. Incorrect loop range causing out-of-bounds access

D. Using map as pointer without allocation

Solution

1. Step 1: Analyze map usage for sums

   The map array uses indices as sums, but sums can be negative, causing invalid indexing.

2. Step 2: Identify impact of negative sums

   Negative sums cause out-of-bound access or wrong counts since array indices can't be negative.

3. Final Answer:

   Array map size is too small for negative sums -> Option A

4. Quick Check:

   Negative sums need offset or different data structure [OK]

Hint: Handle negative sums with offset or hash map [OK]

Common Mistakes:

• Ignoring negative sums in indexing
• Assuming sums are always positive
• Not initializing map for sum 0

5. Given an array arr = {3, 4, 7, 2, -3, 1, 4, 2} and k = 7, how many subarrays sum to k? Use the hash map approach to find the answer.

hard

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Calculate prefix sums and track counts

   Prefix sums: 3,7,14,16,13,14,18,20. Check sums - k in map to count subarrays.

2. Step 2: Count subarrays with sum k=7

   Subarrays: [3,4], [7], [7,2,-3,1], [1,4,2], [4,2, -3,1,4] total 5 subarrays.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Count subarrays summing to 7 = 5 [OK]

Hint: Use prefix sums and hash map to count subarrays fast [OK]

Common Mistakes:

• Missing subarrays with negative numbers
• Counting overlapping subarrays incorrectly
• Not updating hash map counts properly