Problem Statement

Given an integer array arr[] and an integer k, your task is to find the total number of continuous subarrays whose sum equals k.

A subarray is a contiguous non-empty sequence of elements within an array.

LeetCode

https://leetcode.com/problems/subarray-sum-equals-k/

Constraints

1 <= nums.length <= 2 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= k <= 10^7

Examples

Example 1:

Input: arr = [1, 1, 1], k = 2
Output: 2

Explanation:
The subarrays [1, 1] (from index 0 to 1) and [1, 1] (from index 1 to 2) both sum to 2. Hence, there are two subarrays.

Example 2:

Input: arr = [1, 2, 3], k = 3
Output = 2

Explanation:
The subarrays [1, 2] (from index 0 to 1) and [3] (from index 2 to 2) sum to 3.

Example 3:

Input: arr = [10, 2, -2, -20, 10], k = -10
Output: 3

Explanation:
The subarrays [10, 2, -2, -20], [2, -2, -20, 10], and [-20, 10] sum to -10.

Different Approaches

1️⃣ Brute Force Approach (Check All Subarrays) (TLE)

Intuition:

Try every possible subarray, calculate its sum, and check if it equals k.

      0     1     2     3     4     5
   +-----+-----+-----+-----+-----+-----+
   |     |     |     |     |     |     |
   +-----+-----+-----+-----+-----+-----+
   
   Every index can be starting and ending point of the subarray.

Approach:

1. Find all possible subarrays.
2. Find sum and check == target.

Code:

int subarraySum(vector<int>& nums, int k) {
    int count = 0;                  // Initialize a counter to store the number of subarrays with sum equal to k
    int n = nums.size();            // Store the size of the input array for reuse

    // Outer loop to choose the starting index of the subarray
    for (int start = 0; start < n; start++) {
        // Inner loop to choose the ending index of the subarray
        for (int end = start; end < n; end++) {
            int sum = 0;            // Initialize the sum of the current subarray to 0

            // Loop to calculate the sum of the subarray from index 'start' to 'end'
            for (int i = start; i <= end; i++) {
                sum += nums[i];     // Accumulate the sum of elements in the current subarray
            }

            // If the current subarray sum is equal to k, increment the counter
            if (sum == k) count++;
        }
    }

    return count;                   // Return the total count of subarrays with sum equal to k
}

Complexity Analysis:

• Time Complexity:O(n^3)
  • As it involves three nested loops, in worst case.
• Space Complexity:O(1)

2️⃣ Better Brute Force Approach

Intuition:

A subarray is defined by a starting index and an ending index. So, if we can iterate through all possible subarrays, calculate their sum, and check if it equals k, we can count them.

But instead of recalculating the sum from scratch each time (which would take O(n^3)), we can reuse the previous sum as we extend the subarray to the right — reducing the time to O(n^2).

Approach:

1. Loop over all possible starting indices (i) of subarrays.
2. Initialize a sum = 0 for each new starting index.
3. Loop from that index (j = i) to the end of the array.
4. In each iteration:
   1. Add nums[j] to the current sum.
   2. If sum == k, we found a valid subarray, so increment the counter.
5. Finally, return the count of such subarrays.

Dry Run:

nums = [1, 2, 3], k = 3

i = 0:
  sum = 0
  j = 0 → sum = 1     → not equal
  j = 1 → sum = 3     → match! count++
  j = 2 → sum = 6     → no

i = 1:
  sum = 0
  j = 1 → sum = 2     → no
  j = 2 → sum = 5     → no

i = 2:
  sum = 0
  j = 2 → sum = 3     → match! count++

Answer = 2 subarrays → [1,2] and [3]

Code:

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();     // Store the size of the input array
        int total = 0;           // Initialize counter to count subarrays with sum equal to k

        // Loop over each possible starting index of a subarray
        for (int i = 0; i < n; i++) {
            int sum = 0;         // Initialize sum of the current subarray starting at index i

            // Loop over each possible ending index of the subarray starting at index i
            for (int j = i; j < n; j++) {
                sum += nums[j];  // Add current element to the sum

                // If the current subarray sum equals k, increment the total count
                if (sum == k) {
                    total++;
                }
            }
        }

        return total;            // Return the total count of valid subarrays
    }
};

Complexity Analysis:

• Time Complexity:O(n^2)
  • As it involves two nested loops.
• Space Complexity:O(1)

3️⃣ Prefix Sum (Better Approach) (TLE)

Intuition:

It is the enhance version of the first approach of three nested loops. It is just replacing the innermost loop where we find the sum by iterating over the range. Here we find the same using the prefix sum array technique. The innermost loop will be calculating sum in O(1).

Approach:

1. Step 1: Prefix Sum Precomputation
   1. Construct a prefix sum array prefixSums where:
      1. prefixSums[i] stores the sum of all elements from nums[0] to nums[i].

   2. This helps in computing the sum of any subarray nums[start..end] in constant time using:

      subarraySum = prefixSums[end] - prefixSums[start - 1]
      

2. Step 2: Iterate Over All Subarrays
   1. Use two nested loops:
      1. Outer loop chooses the start index.
      2. Inner loop chooses the end index (≥ start).
   2. For each subarray nums[start..end], use the prefix sums to get the total in O(1) time.
   3. If the subarray sum equals k, increment the count.
3. Step 3: Return the count
   1. After checking all subarrays, return the final count.

Code:

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();

        // Step 1: Create a prefix sum array to store cumulative sums up to each index
        vector<int> prefixSums(n, 0);    // prefixSums[i] = sum of nums[0] to nums[i]
        int runningSum = 0;

        for (int i = 0; i < n; i++) {
            runningSum += nums[i];       // Keep adding the current number to get cumulative sum
            prefixSums[i] = runningSum;  // Store the running sum in the prefix sum array
        }

        int count = 0;   // Initialize counter to store number of subarrays with sum = k

        // Step 2: Iterate over all pairs of start and end indices
        for (int start = 0; start < n; start++) {
            for (int end = start; end < n; end++) {
                // Calculate the sum of subarray nums[start..end] using prefix sums
                int subarraySum = (start == 0) 
                                    ? prefixSums[end]                       // If start is 0, sum is directly prefixSums[end]
                                    : prefixSums[end] - prefixSums[start-1]; // Else subtract prefixSums before 'start'

                // Step 3: If the subarray sum is equal to k, increment the count
                if (subarraySum == k) {
                    count++;
                }
            }
        }

        return count;  // Return the total number of subarrays whose sum equals k
    }
};

Complexity Analysis:

• Time Complexity:O(n^2) + O(n)
  • Due to double loop for checking subarrays.
  • O(n): for prefix computation.
• Space Complexity:O(n)
  • For the prefix sum array.

2️⃣ Prefix Sum + HashMap

Intuition:

Imagine you are walking through the array and keeping track of the total sum of elements seen so far (we call it the running sum or prefix sum).

Now at any point, if you know that:

current running sum - previous running sum = target

Then the array between those two points must sum to target.

Approach:

1. Step 1: Initialize
   1. A hash map prefixSumCount to store frequency of prefix sums.
   2. prefixSumCount[0] = 1 to handle subarrays starting from index 0.
   3. runningSum = 0 to keep the cumulative sum.
   4. totalSubarrays = 0 to keep the count of valid subarrays.
2. Step 2: Traverse the array
   1. For each element in the array:
      1. Add the element to runningSum.
      2. Calculate the requiredSum as runningSum - target.
      3. If requiredSum exists in prefixSumCount, it means there are one or more subarrays ending at current index that sum to target.
      4. Add the frequency of requiredSum to totalSubarrays.
      5. Update the map by increasing the count of runningSum.
3. Step 3: Return the count.

Dry Run:

       +-----+-----+-----+-----+-----+
nums = |  1  |  2  |  1  |  2  |  1  |
       +-----+-----+-----+-----+-----+
          0     1     2     3     4
k = 3

We want to find how may subarrays sum to 3.

4 subarrays with sum 3.

Code:

class Solution {
public:
    int subarraySum(vector<int>& nums, int target) {
        int n = nums.size();

        // This map will store the frequency of prefix sums
        unordered_map<int, int> prefixSumCount;

        // Important: Initialize with 0 sum having 1 count
        // This handles the case where a subarray from index 0 has sum = target
        prefixSumCount[0] = 1;

        int runningSum = 0;        // To store cumulative sum while iterating
        int totalSubarrays = 0;    // Final count of subarrays that sum to target

        // Traverse the array
        for (int i = 0; i < n; i++) {
            runningSum += nums[i];  // Update cumulative sum

            int requiredSum = runningSum - target;  // What sum do we need earlier to form the current subarray

            // Check if this requiredSum was seen before
            // If yes, it means there are subarrays that sum to target ending at current index
            if (prefixSumCount.find(requiredSum) != prefixSumCount.end()) {
                totalSubarrays += prefixSumCount[requiredSum];  // Add how many times it occurred
            }

            // Record the current runningSum in the map
            prefixSumCount[runningSum]++;
        }

        return totalSubarrays;  // Return total count of valid subarrays
    }
};

Complexity Analysis:

• Time Complexity:O(n)
• Space Complexity:O(n)

https://leetcode.com/problems/continuous-subarray-sum/discuss/5276981/Prefix-Sum-%2B-HashMap-Patterns-(-7-problems-)

https://www.hellointerview.com/learn/code/prefix-sum/overview