Subsequence Sum Occurrences — Problem Statement & Solution Guide
Problem Description
You are given an array of integers and a target value. Count how many contiguous subarrays have a sum equal to the target. A subarray is a sequence of consecutive elements taken from the original array. The input consists of three lines: the first line contains the integer n (the number of elements), the second line lists the n integers separated by spaces, and the third line contains the target sum k. Output a single integer: the total number of subarrays whose elements sum to k.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Subsequence Sum Occurrences"
WHY DOES IT MATTER?
Counting subarrays with a target sum is a classic example of converting a quadratic search into a linear one using cumulative information. Mastering this pattern equips engineers to solve a wide range of range‑query problems efficiently, a skill frequently tested in coding interviews.
OPTIMIZATION CHALLENGE
The key insight is recognizing that the subarray sum condition can be rewritten as a relationship between two prefix sums, allowing us to count matches via a frequency map instead of enumerating every pair.
REAL-WORLD CONNECTION
In streaming analytics, you often need to detect when a rolling metric (e.g., total transactions in the last minute) hits a threshold. Maintaining a running sum and a hash of past aggregates lets you trigger alerts in constant time per event, mirroring the prefix‑sum hashmap technique.
During an interview, compute the running prefix sum on the fly, update the answer using map.getOrDefault(currentSum - target, 0), then increment the map count for currentSum. This one‑pass flow shows both correctness and efficiency.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The fundamental insight for counting subarrays with a given sum lies in prefix sums. A prefix sum P[i] represents the total of the first i elements; the sum of any subarray [l, r] can be expressed as P[r] - P[l-1]. By rearranging the equation to P[r] - target = P[l-1], we see that for each ending index r we only need to know how many previous prefix sums equal P[r] - target. Storing frequencies of all encountered prefix sums in a hash map enables O(1) look‑ups, turning an O(n²) enumeration into a linear scan.
A naive double‑loop enumerates every possible start and end pair, recomputing sums or using a cumulative array, which quickly exceeds time limits for n up to 10⁵ or more. The optimal paradigm—often called the "prefix sum with hashmap" or "cumulative frequency" technique—leverages constant‑time map queries to maintain a running count of viable start positions, achieving linear time while using linear extra space for the frequency table.
Interview Questions on This Problem
Q1How would you modify the solution if the array could contain very large integers that might cause prefix sum overflow?
Use a 64‑bit integer type (e.g., long long in C++ or long in Java) for the running sum and hashmap keys; if the language supports arbitrary precision (like Python's int), it handles overflow automatically. Additionally, you can normalize values by subtracting a constant offset if needed, but typically just using a larger integer type suffices.
Q2Can this algorithm be adapted to count subarrays whose sum is divisible by k?
Yes. Instead of storing exact prefix sums, store the remainder of each prefix sum modulo k. For each new prefix, the number of previous prefixes with the same remainder gives the count of subarrays whose sum is divisible by k, because (P[r] - P[l-1]) % k == 0 ⇔ P[r] % k == P[l-1] % k.
Q3What is the time‑space trade‑off if you are constrained to O(1) extra space?
With O(1) extra space you cannot keep a frequency map, so you must revert to the O(n²) brute‑force method or use a two‑pointer sliding window, which only works for non‑negative numbers. For arbitrary integers, achieving linear time without extra space is impossible because you need to remember past prefix sums.
Examples
Input
5 1 2 3 4 5 5
Output
2
Explanation: The subarrays that sum to 5 are [2,3] (indices 1–2) and [5] (index 4). No other contiguous segment totals 5, so the answer is 2.
Input
4 1 -1 1 -1 0
Output
4
Explanation: All subarrays with sum 0 are: [1,-1] (0–1), [1,-1,1,-1] (0–3), [-1,1] (1–2), and [1,-1] (2–3). Thus there are 4 such subarrays.
Input
3 0 0 0 0
Output
6
Explanation: Every possible subarray of the array [0,0,0] sums to 0. There are 3*(3+1)/2 = 6 subarrays in total, so the answer is 6.
Constraints
- 1 <= n <= 100000
- -1000000000 <= nums[i] <= 1000000000
- -100000000000000 <= k <= 100000000000000
Optimal Approach & Strategy
Maintain a running prefix sum and a hash map of its frequencies; for each element, add the count of (prefix‑sum − target) from the map to the answer, then update the map with the current prefix sum. This yields a single‑pass O(n) solution.
Brute Force Approach
Iterate over every possible start index, then for each start, expand the end index while accumulating the sum; increment a counter whenever the sum equals the target. This double loop checks O(n²) subarrays.
Verified Code Solutions
function solution(nums, targetSum) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
let currentSum = 0;
for (let j = i; j < nums.length; j++) {
currentSum += nums[j];
if (currentSum === targetSum) {
count++;
}
}
}
return count;
}class Solution {
public:
int solution(vector<int>& nums, int targetSum) {
int count = 0;
for (int i = 0; i < nums.size(); i++) {
int currentSum = 0;
for (int j = i; j < nums.size(); j++) {
currentSum += nums[j];
if (currentSum === targetSum) {
count++;
}
}
}
return count;
}
};class Solution {
public int solution(int[] nums, int targetSum) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
int currentSum = 0;
for (int j = i; j < nums.length; j++) {
currentSum += nums[j];
if (currentSum === targetSum) {
count++;
}
}
}
return count;
}
}def solution(nums, targetSum):
count = 0
for i in range(len(nums)):
currentSum = 0
for j in range(i, len(nums)):
currentSum += nums[j]
if currentSum === targetSum:
count += 1
return countfunction solution(nums, targetSum) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
let currentSum = 0;
for (let j = i; j < nums.length; j++) {
currentSum += nums[j];
if (currentSum === targetSum) {
count++;
}
}
}
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.