Introduction

The Subarray Sum Equals K problem involves finding the total number of contiguous subarrays whose sum is equal to a given value k.

Given an array arr[] of size n and an integer k, the task is to count all subarrays having sum exactly equal to k.

This is one of the most important Prefix Sum + HashMap problems and helps in understanding subarray processing, cumulative sums, and efficient lookup techniques.

Example

Input: arr[] = [1, 2, 1, 2, 1]k = 3
Output: 4
Explanation:
Subarrays with sum 3 are:
[1, 2]
[2, 1]
[1, 2]
[2, 1]
Total Count = 4

Input: arr[] = [3, 1, -1, 2, 4]
k = 5
Output: 2
Explanation:
Subarrays with sum 5 are:
[3, 1, -1, 2]
[1, -1, 2, 4]
Total Count = 2

Constraints

  1 <= n <= 10^5
-10^9 <= arr[i] <= 10^9
-10^9 <= k <= 10^9

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Generate all possible subarrays
  2. Calculate the sum of every subarray
  3. Count subarrays whose sum equals k.

This approach is easy to understand but repeatedly calculating sums increases time complexity.

Steps

  1. Traverse all starting indices.
  2. For every starting index:
    • generate subarrays
  3. Calculate current subarray sum.
  4. If sum equals k:
    • increment count
  5. Return final count.

Dry Run

Input Array: [1, 2, 1, 2, 1]k = 3
Subarray [1]:
Sum = 1
Subarray [1, 2]:
Sum = 3
Valid Subarray
Count = 1
Subarray [2, 1]:
Sum = 3
Count = 2
Subarray [1, 2]:
Sum = 3
Count = 3
Subarray [2, 1]:
Sum = 3
Count = 4
Final Result:
4

Brute Force Code 

Complexity Analysis

Time Complexity: O(n²)Explanation:
All possible subarrays are generated and checked.

Space Complexity: O(1)
Explanation:
No extra data structures are used.

Approach 2 : Optimized Solution (Prefix Sum + HashMap)

Explanation

Instead of generating all subarrays, we can use:

  1. Prefix Sum
  2. HashMap

The idea is:

If:

 currentPrefixSum - previousPrefixSum = k

Then:

 previousPrefixSum = currentPrefixSum - k

So:

  •  if (currentSum - k) already exists,
    • then a valid subarray exists.

    The HashMap stores:

    • prefix sum → frequency

    This allows subarrays to be counted efficiently.

    Steps

    1.  Initialize:
      • prefixSum = 0
      • count = 0
      • hashmap with {0  : 1}
    2. Traverse the array.
    3. Add current element to prefix sum.
    4. Check if:
      • (prefixSum - k) exists
    5. Add its frequency to count.
    6. Store/update current prefix sum frequency.
    Dry Run
    Input Array: [1, 2, 1, 2, 1]k = 3
    Initially:
    prefixSum = 0
    count = 0
    HashMap:
    {0:1}
    Traverse 1:
    prefixSum = 1
    1 - 3 = -2
    Not found
    Store:
    {0:1, 1:1}
    Traverse 2:
    prefixSum = 3
3 - 3 = 0
    Found in map
    Count = 1
    Store:
    {0:1, 1:1, 3:1}
    Traverse 1:
    prefixSum = 4
    4 - 3 = 1
    Found in map
    Count = 2
    Continue similarly...
    Final Result:
    4

    Optimized Code

    Complexity Analysis

    Time Complexity: O(n)Explanation:
Each element is processed once using HashMap lookups.

    Space Complexity: O(n)
    Explanation:
HashMap stores prefix sum frequencies.

    Edge Cases

    1. Array contains negative numbers
    2. Multiple overlapping subarrays
    3. No valid subarray exists
    4. Array contains zeros
    5. Entire array sum equals k

    Why This Problem is Important

    This problem helps in understanding:

    1. Prefix Sum Technique
    2. HashMap optimization
    3. Subarray processing
    4. Efficient counting techniques
    5. Cumulative computations

    It is one of the most important Prefix Sum interview problems.

    Real-World Applications

    Prefix Sum and hashing concepts are used in:

    1. Financial analytics
    2. Streaming systems
    3. Time-series processing
    4. Data aggregation
    5. Pattern detection systems

    Common Mistakes

    1. Forgetting hashmap initialization {0:1}
    2. Incorrect prefix sum updates
    3. Using sliding window for negative numbers
    4. Overwriting frequencies incorrectly

    Interview Tips

    Interviewers often expect:

    1. Prefix Sum optimization
    2. HashMap usage
    3. O(n) solution

    Always explain why storing prefix sum frequencies helps count valid subarrays efficiently.

    Related Questions

    1. Running Sum
    2. Longest Subarray with Sum K
    3. Count Prefix Sum
    4. Range Sum Query
    5. Maximum Size Subarray Sum Equals K

    Final Takeaway

    The Subarray Sum Equals K problem is a fundamental Prefix Sum and HashMap problem that teaches efficient subarray counting and cumulative computation techniques. Understanding this problem builds a strong foundation for advanced hashing, prefix sum, and range query interview problems.