Subarray Sum Counter 2 — Problem Statement & Solution Guide
Problem Description
Given an array of integers and a target sum, design an algorithm to count the number of subarrays with a sum equal to the target sum. A subarray is a contiguous subset of the array.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Subarray Sum Counter 2"
WHY DOES IT MATTER?
The prefix-sum-with-hashmap pattern reduces a quadratic problem to linear time, which is essential for interview success and real-world scalability. It demonstrates mastery of cumulative data structures and hash-based lookups, both of which are high-value skills for software engineers.
OPTIMIZATION CHALLENGE
The core insight is recognizing that subarray sums can be expressed as differences of prefix sums, allowing the use of a hash map to count complementary sums in constant time per element.
REAL-WORLD CONNECTION
Consider a financial trading platform tracking cumulative profits over time. Detecting periods where the profit equals a target threshold is analogous to finding subarrays with a given sum; the same prefix-sum logic can be applied to real-time analytics dashboards.
When explaining this pattern in an interview, emphasize the transformation from a nested-loop problem to a single-pass hash map solution, and be ready to discuss edge cases like negative numbers and zero-sum subarrays.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The classic subarray sum problem can be solved in linear time by leveraging the concept of prefix sums and a hash map. A prefix sum at index i is the cumulative sum of all elements up to i; if we denote it as pre[i], then the sum of a subarray from l to r is pre[r] - pre[l-1]. To find subarrays that sum to a target k, we need to count pairs (l, r) such that pre[r] - pre[l-1] = k, which rearranges to pre[l-1] = pre[r] - k. By iterating through the array once and maintaining a hash map that records the frequency of each prefix sum seen so far, we can query in O(1) how many previous prefixes satisfy the equation for the current pre[r]. This transforms the problem from an O(n^2) brute force to an O(n) solution.
Naive approaches typically involve nested loops to examine every possible subarray, leading to quadratic time and unacceptable performance on large inputs (e.g., n > 10^5). Even an O(n^2) approach with early pruning fails because the number of subarrays grows as n(n+1)/2. The optimal paradigm—prefix sums with a hash map—provides a linear-time, linear-space solution that scales to massive datasets and is the standard technique taught in algorithm courses and interview prep.
The key insight is that the subarray sum problem is essentially a two-sum problem on the set of prefix sums. By treating the prefix sums as a running total and using a dictionary to look up complementary sums, we avoid recomputing sums for overlapping subarrays. This pattern is widely applicable to problems involving contiguous segments, such as finding the longest subarray with a given sum, counting subarrays with sum less than k, or detecting zero-sum subarrays.
Interview Questions on This Problem
Q1How would you modify the algorithm if the array contains only positive integers?
With all positive numbers, the two-pointer sliding window technique can be used: maintain a left and right pointer, expand the right pointer while the window sum is less than the target, and shrink from the left when it exceeds. This yields an O(n) solution without a hash map, but the prefix-sum method still works and is more general.
Q2In a distributed system, how would you parallelize counting subarrays across multiple nodes?
Partition the array into chunks, compute prefix sums locally, and propagate the last prefix sum of each chunk to the next. Each node counts subarrays within its chunk using the hash map, then adjusts counts for subarrays spanning chunks by combining prefix sums from preceding nodes. This requires careful handling of boundary conditions but preserves linear overall complexity.
Q3What is the space-time tradeoff if you need to support dynamic updates to the array?
For dynamic updates, a Binary Indexed Tree (Fenwick) or Segment Tree can maintain prefix sums in O(log n) per update and query. However, counting subarrays with a target sum becomes more complex; one approach is to maintain a multiset of prefix sums and update it accordingly, but the time per query may increase to O(n log n) unless additional structure is used.
Examples
Input
[1, 4, 2, 3]
Output
2
Explanation: Step-by-step: 1. Calculate prefix sums: [1, 5, 7, 10]. 2. Iterate through prefix sums to find pairs that sum up to the target (5). 3. The subarrays [1, 4] and [4, 2, 3, -3] sum up to 5, giving 2 subarrays.
Input
[1, -1, 1, -1, 1, -1]
Output
5
Explanation: Step-by-step: 1. Calculate prefix sums: [1, 0, 1, 0, 1, 0]. 2. Iterate through prefix sums to find pairs that sum up to the target (0). 3. The subarrays [1, -1], [-1, 1], [1, -1], [-1, 1], and [1, -1, 1, -1] sum up to 0, giving 5 subarrays.
Constraints
- 1 <= arr.length <= 10^5
- -10^9 <= arr[i] <= 10^9
- -10^9 <= target_sum <= 10^9
Optimal Approach & Strategy
Maintain a running prefix sum and a hash map of prefix frequencies. For each new sum, add to the answer the count of (current sum - target) in the map, then update the map with the current sum. This runs in O(n) time and O(n) space.
Brute Force Approach
Check every possible start and end index, compute the sum of the subarray, and increment a counter if it equals the target. This takes O(n^2) time and O(1) space.
Verified Code Solutions
function solution(nums, target) {
let prefixSum = 0;
let count = 0;
let prefixSumMap = new Map();
prefixSumMap.set(0, 1);
for (let num of nums) {
prefixSum += num;
if (prefixSumMap.has(prefixSum - target)) {
count += prefixSumMap.get(prefixSum - target);
}
if (prefixSumMap.has(prefixSum)) {
prefixSumMap.set(prefixSum, prefixSumMap.get(prefixSum) + 1);
} else {
prefixSumMap.set(prefixSum, 1);
}
}
return count;
}class Solution {
public:
int solution(vector<int>& nums, int target) {
int prefixSum = 0;
int count = 0;
unordered_map<int, int> prefixSumMap;
prefixSumMap[0] = 1;
for (int num : nums) {
prefixSum += num;
if (prefixSumMap.find(prefixSum - target) != prefixSumMap.end()) {
count += prefixSumMap[prefixSum - target];
}
if (prefixSumMap.find(prefixSum) != prefixSumMap.end()) {
prefixSumMap[prefixSum]++;
} else {
prefixSumMap[prefixSum] = 1;
}
}
return count;
}
};class Solution {
public int solution(int[] nums, int target) {
int prefixSum = 0;
int count = 0;
Map<Integer, Integer> prefixSumMap = new HashMap<>();
prefixSumMap.put(0, 1);
for (int num : nums) {
prefixSum += num;
if (prefixSumMap.containsKey(prefixSum - target)) {
count += prefixSumMap.get(prefixSum - target);
}
if (prefixSumMap.containsKey(prefixSum)) {
prefixSumMap.put(prefixSum, prefixSumMap.get(prefixSum) + 1);
} else {
prefixSumMap.put(prefixSum, 1);
}
}
return count;
}
}def solution(nums, target):
prefix_sum = 0
count = 0
prefix_sum_map = {0: 1}
for num in nums:
prefix_sum += num
if prefix_sum - target in prefix_sum_map:
count += prefix_sum_map[prefix_sum - target]
if prefix_sum in prefix_sum_map:
prefix_sum_map[prefix_sum] += 1
else:
prefix_sum_map[prefix_sum] = 1
return countfunction solution(nums, target) {
let prefixSum = 0;
let count = 0;
let prefixSumMap = new Map();
prefixSumMap.set(0, 1);
for (let num of nums) {
prefixSum += num;
if (prefixSumMap.has(prefixSum - target)) {
count += prefixSumMap.get(prefixSum - target);
}
if (prefixSumMap.has(prefixSum)) {
prefixSumMap.set(prefixSum, prefixSumMap.get(prefixSum) + 1);
} else {
prefixSumMap.set(prefixSum, 1);
}
}
return count;
}Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.