Find Subarrays with Sum K - C++ Algorithm Guide
Quick Summary: To find the number of continuous subarrays having a sum exactly equal to K, the most efficient approach is to use a prefix sum technique paired with a hash map. By tracking the running sum and storing its frequencies, you can check if currSum - K exists in the map, effectively reducing the time complexity from O(N²) to O(N).
Understanding the Problem
Given an unsorted array of integers, you must find the total number of continuous subarrays where the elements add up to a specific integer k. This is a classic coding interview problem that tests your ability to optimize nested loops using auxiliary data structures.
Examples
Input: arr = [10, 2, -2, -20, 10], k = -10 Output: 3 Explanation: Subarrays: arr[0...3], arr[1...4], arr[3...4] have sum exactly equal to -10.
Input: arr = [9, 4, 20, 3, 10, 5], k = 33 Output: 2 Explanation: Subarrays: arr[0...2], arr[2...4] have sum exactly equal to 33.
Input: arr = [1, 3, 5], k = 0 Output: 0 Explanation: No subarray with 0 sum.
Constraints
- 1 ≤ arr.size() ≤ 105
- -103 ≤ arr[i] ≤ 103
- -107 ≤ k ≤ 107
Optimized C++ Solution Using Prefix Sums
A naive approach would be to check every possible subarray using two nested loops. However, this yields a time complexity of O(N²), which is too slow for an array size of 105. Instead, we can optimize this to O(N) using a prefix sum and an unordered_map in C++.
As we iterate through the array, we maintain a currSum. If currSum - k exists in our map, it means there is a subarray ending at the current index which sums up to k. We then add the frequency of currSum - k to our result counter.
class Solution {
public:
int countSubarrays(vector<int> &arr, int k) {
// unordered_map to store prefix sums frequencies
unordered_map<int, int> prefixSums;
int res = 0;
int currSum = 0;
for (int i = 0; i < arr.size(); i++) {
// Add current element to sum so far.
currSum += arr[i];
// If currSum is equal to desired sum, then a new
// subarray is found. So increase count of subarrays.
if (currSum == k)
res++;
// Check if the difference exists in the prefixSums map.
if (prefixSums.find(currSum - k) != prefixSums.end())
res += prefixSums[currSum - k];
// Add currSum to the set of prefix sums.
prefixSums[currSum]++;
}
return res;
}
};Frequently Asked Questions
What is the optimal time complexity for finding subarrays with sum K?
The optimal time complexity is O(N) using a prefix sum array combined with an unordered map (hash table) to store frequencies of prefix sums. This allows us to look up the required difference in O(1) average time.
Why does the prefix sum approach work for finding a target sum?
The prefix sum approach works because the sum of any continuous subarray from index i to j can be expressed as the difference between the prefix sum up to j and the prefix sum up to i-1. By keeping track of the frequencies of all previous prefix sums, we can quickly count how many times a valid starting point occurred.