Subarray Sum Counter — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Hashing and solve the Subarray Sum Counter problem optimally.
O(n)O(n)Problem Description
Given an integer array nums and an integer target, determine how many contiguous subarrays of nums have a sum exactly equal to target. Return this count as a 64‑bit integer. The algorithm must run in linear time and use linear or constant extra space, handling large positive or negative values without overflow.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Subarray Sum Counter"
WHY DOES IT MATTER?
Counting sub‑arrays with a given sum is a classic example of transforming a quadratic problem into linear time using prefix sums and hash‑based frequency counting. Mastery of this pattern unlocks efficient solutions for many range‑query and cumulative‑frequency problems.
OPTIMIZATION CHALLENGE
The breakthrough is recognizing that the condition "sub‑array sum = target" can be rewritten as "previous prefix = current prefix - target". This re‑expression lets us replace the inner loop with a constant‑time hash lookup, collapsing O(n^2) to O(n).
REAL-WORLD CONNECTION
Think of a financial ledger where each entry is a transaction amount. The prefix sum represents the account balance after each transaction. Finding how many periods resulted in a net change equal to a target is analogous to counting sub‑arrays, and the hash map acts like a quick lookup table of past balances.
When coding, initialize the map with {0:1} to handle sub‑arrays that start at index 0, and always use a 64‑bit integer for both the running prefix and the answer to avoid overflow on large inputs.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The Subarray Sum Counter problem asks for the number of contiguous sub‑arrays whose elements add up to a given target. The naïve solution enumerates every possible start index i and end index j, computes the sum of nums[i..j] and checks against target. This double loop incurs O(n^2) time and quickly becomes infeasible for n in the order of 10^5 or larger, especially when the array contains both positive and negative numbers that prevent early termination. Moreover, repeated summation leads to integer overflow if 64‑bit accumulation is not used.
The optimal paradigm leverages prefix sums combined with a hash map (or unordered_map) that records how many times each cumulative sum has been seen while scanning the array once. Let prefix[k] be the sum of the first k elements. A sub‑array (i, j] sums to target exactly when prefix[j] - prefix[i] = target, i.e., prefix[i] = prefix[j] - target. By maintaining a frequency table of previously observed prefix values, each new prefix[j] can instantly reveal how many i satisfy the equation, yielding a linear‑time solution.
Because we only store a single hash map of at most n+1 entries, the extra space is O(n) in the worst case (or O(1) if we treat the map as auxiliary). The approach works for arbitrary integer ranges, including large positive or negative values, as long as the accumulator is a 64‑bit signed integer, thereby avoiding overflow while preserving exact counts.
Interview Questions on This Problem
Q1How would you modify the solution if the problem asked for the number of sub‑arrays with sum *at most* target?
Maintain a sorted data structure (e.g., balanced BST or Fenwick tree) of prefix sums; for each new prefix, count how many previous prefixes are ≥ prefix - target. This yields O(n log n) time. Alternatively, if all numbers are non‑negative, a sliding window can achieve O(n).
Q2Why does the hash‑map solution still work when the array contains negative numbers, whereas a two‑pointer sliding‑window fails?
The hash‑map relies on the algebraic identity prefix[j] - prefix[i] = target, which holds regardless of sign. A sliding window assumes monotonic growth of the window sum, which is broken by negatives, making it impossible to guarantee correctness without backtracking.
Q3In a distributed system processing a massive stream of numbers, how could you compute the sub‑array count for a fixed target without storing the entire stream?
Use a streaming algorithm that keeps only the current prefix sum and a hash map of its frequencies; the map size is bounded by the number of distinct prefix sums seen so far, which can be pruned or approximated (e.g., using Count‑Min Sketch) if memory is constrained. The count can be updated on‑the‑fly as each new element arrives.
Examples
Input
nums = [1,2,3,2,1], target = 5
Output
2
Explanation: The subarrays that sum to 5 are [2,3] (indices 1‑2) and [3,2] (indices 2‑3). No other contiguous segment adds up to 5, so the answer is 2.
Input
nums = [0,0,0], target = 0
Output
6
Explanation: Every possible subarray of a zero‑filled array sums to 0. With n=3, the number of subarrays is n·(n+1)/2 = 3·4/2 = 6.
Input
nums = [-1,2,-1,2,-1], target = 2
Output
4
Explanation: Valid subarrays are: [-1,2,-1,2] (0‑3), [2] (1‑1), [2,-1,2,-1] (1‑4), and [2] (3‑3). Hence the count is 4.
Constraints
- 1 <= nums.length <= 100000
- -1000000000 <= nums[i] <= 1000000000
- -100000000000000 <= target <= 100000000000000
Optimal Approach & Strategy
Maintain a cumulative sum and a hash map of its frequencies; for each element, add the count of (cumulativeSum - target) from the map to the answer, then update the map with the current cumulative sum. This yields O(n) time and O(n) space.
Brute Force Approach
Enumerate every possible start index and extend the sub‑array while accumulating the sum, checking for equality with target each time. This double loop costs O(n^2) time.
Code Solutions
function subarraySumCount(nums, target) {
const freq = new Map();
freq.set(0,1);
let pref=0, ans=0;
for(const x of nums){
pref+=x;
const need = pref - target;
if(freq.has(need)) ans+=freq.get(need);
freq.set(pref, (freq.get(pref)||0)+1);
}
return ans;
}
const fs = require('fs');
function main(){
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
let idx=0;
const n=data[idx++];
const nums=data.slice(idx, idx+n); idx+=n;
const target=data[idx];
console.log(subarraySumCount(nums,target));
}
main();#include <bits/stdc++.h>
using namespace std;
long long subarraySumCount(const vector<int>& nums, long long target) {
unordered_map<long long,long long> freq;
freq[0]=1; // empty prefix
long long pref=0, ans=0;
for(int x: nums){
pref+=x;
auto it = freq.find(pref-target);
if(it!=freq.end()) ans+=it->second;
++freq[pref];
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<int> nums(n);
for(int i=0;i<n;++i) cin>>nums[i];
long long target; cin>>target;
cout<<subarraySumCount(nums,target);
return 0;
}import java.io.*;
import java.util.*;
public class Main {
public static long subarraySumCount(int[] nums, long target) {
Map<Long, Long> freq = new HashMap<>();
freq.put(0L, 1L);
long pref = 0L;
long ans = 0L;
for (int x : nums) {
pref += x;
long need = pref - target;
ans += freq.getOrDefault(need, 0L);
freq.put(pref, freq.getOrDefault(pref, 0L) + 1);
}
return ans;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line == null || line.isEmpty()) return;
int n = Integer.parseInt(line.trim());
int[] nums = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(st.nextToken());
long target = Long.parseLong(br.readLine().trim());
System.out.println(subarraySumCount(nums, target));
}
}import sys
from collections import defaultdict
def subarray_sum_count(nums, target):
freq = defaultdict(int)
freq[0]=1
pref=0
ans=0
for x in nums:
pref+=x
ans+=freq[pref-target]
freq[pref]+=1
return ans
def main():
data=list(map(int, sys.stdin.read().strip().split()))
if not data:
return
n=data[0]
nums=data[1:1+n]
target=data[1+n]
print(subarray_sum_count(nums,target))
if __name__=="__main__":
main()function subarraySumCount(nums, target) {
const freq = new Map();
freq.set(0,1);
let pref=0, ans=0;
for(const x of nums){
pref+=x;
const need = pref - target;
if(freq.has(need)) ans+=freq.get(need);
freq.set(pref, (freq.get(pref)||0)+1);
}
return ans;
}
const fs = require('fs');
function main(){
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length===0) return;
let idx=0;
const n=data[idx++];
const nums=data.slice(idx, idx+n); idx+=n;
const target=data[idx];
console.log(subarraySumCount(nums,target));
}
main();Asked in Top Tech Interviews
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.