Subarray Sum Equals K Using Hash Map in DSA Python - 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 list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def subarray_sum(nums, k):
    count = 0
    current_sum = 0
    sums = {0: 1}
    for num in nums:
        current_sum += num
        if current_sum - k in sums:
            count += sums[current_sum - k]
        sums[current_sum] = sums.get(current_sum, 0) + 1
    return count

This code counts how many continuous parts of the list add up exactly to k using a hash map.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: One loop through the list, checking and updating the hash map.
• How many times: Once for each number in the list (n times).

How Execution Grows With Input

Each new number adds a fixed amount of work: updating sums and checking the map.

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

Pattern observation: Operations grow directly with the size of the list.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows in a straight line with the list size.

Common Mistake

[X] Wrong: "Because of the nested map check, this must be O(n²)."

[OK] Correct: The map check is a quick lookup, not a loop, so it stays O(1) each time.

Interview Connect

Understanding this helps you solve many problems where you track sums or counts efficiently.

Self-Check

"What if we used a list instead of a hash map for sums? How would the time complexity change?"