Subarray Sum Finder — Problem Statement & Solution Guide
Problem Description
Given an array of integers nums and an integer K, determine how many contiguous subarrays of nums have a sum that equals exactly K. The input consists of three lines: the first line contains an integer n, the number of elements in nums; the second line contains n space‑separated integers representing the array; the third line contains the integer K. The output is a single integer: the count of subarrays whose elements sum to K.
The task requires an efficient solution that runs in linear time with respect to the length of the array, using a prefix‑sum technique combined with a hash map to track the frequency of prefix sums encountered so far.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Subarray Sum Finder"
WHY DOES IT MATTER?
The prefix sum and hashing pattern is essential for efficiently solving problems involving contiguous subarrays and sum constraints. It transforms a seemingly O(n^2) problem into an O(n) solution by leveraging the mathematical relationship between prefix sums and subarray sums.
OPTIMIZATION CHALLENGE
The key insight is recognizing that the sum of a subarray can be expressed as the difference of two prefix sums. By storing prefix sums in a hash map, we can efficiently count pairs of prefix sums that differ by K, reducing the time complexity from O(n^2) to O(n).
REAL-WORLD CONNECTION
This pattern is analogous to financial transaction analysis, where one might need to count the number of time periods (subarrays) where the net change in account balance equals a specific amount. Prefix sums represent cumulative balances, and hashing allows quick lookup of past balances to identify matching periods.
During interviews, clearly articulate the transformation from subarray sums to prefix sum differences. Emphasize the use of a hash map for O(1) lookups and mention edge cases like negative numbers and zero values. This demonstrates a deep understanding of the algorithm's robustness.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The naive approach to finding subarrays with a specific sum involves iterating through all possible start and end indices, calculating the sum for each subarray, and checking if it equals K. This results in O(n^2) time complexity, which becomes prohibitive for large arrays (e.g., n = 10^5). The key insight to optimize this is recognizing that the sum of a subarray from index i to j can be expressed as the difference between two prefix sums: prefixSum[j+1] - prefixSum[i] = K. This transforms the problem into finding pairs of prefix sums that differ by K.
By maintaining a running prefix sum as we iterate through the array, we can use a hash map to store the frequency of each prefix sum encountered so far. For each current prefix sum, we check if (currentPrefixSum - K) exists in the hash map. If it does, the count of such previous prefix sums indicates how many subarrays ending at the current index have a sum of K. This reduces the time complexity to O(n) because each element is processed once, and hash map lookups are O(1) on average.
This technique is a classic application of the prefix sum and hashing paradigm. It is particularly powerful for problems involving contiguous subarrays and sum constraints. The space complexity is O(n) in the worst case, as the hash map may store up to n distinct prefix sums. This approach is widely used in competitive programming and technical interviews due to its elegance and efficiency.
Interview Questions on This Problem
Q1How would you modify the algorithm to handle negative numbers in the array?
The prefix sum and hashing approach naturally handles negative numbers. Unlike sliding window techniques, which rely on monotonicity, the prefix sum method does not assume all elements are positive. The hash map stores all prefix sums, including those that decrease due to negative values, ensuring correct counting of subarrays with sum K.
Q2What is the time and space complexity of the optimal solution, and why is it better than the brute force approach?
The optimal solution has O(n) time complexity because each element is processed once, and hash map operations are O(1) on average. The space complexity is O(n) due to the hash map storing prefix sums. This is significantly better than the brute force O(n^2) time complexity, especially for large inputs.
Q3Can this approach be extended to find subarrays with a sum divisible by K?
Yes, by storing the remainder of each prefix sum when divided by K in the hash map. For each current prefix sum, check if (currentRemainder - targetRemainder) mod K exists in the map. This allows counting subarrays with sums divisible by K in O(n) time.
Examples
Input
nums = [1, 2, 3], k = 3
Output
2
Explanation: 1. Compute prefix sums: [0, 1, 3, 6]. 2. For each prefix sum s, look for s-K in the hash map. 3. At index 1 (s=1), 1-3=-2 not found. 4. At index 2 (s=3), 3-3=0 found once → one subarray [1,2]. 5. At index 3 (s=6), 6-3=3 found once → one subarray [3]. 6. Total count = 2.
Input
nums = [1, 1, 1, 1], k = 2
Output
3
Explanation: 1. Prefix sums: [0, 1, 2, 3, 4]. 2. For s=2 (index 2), 2-2=0 found → subarray [1,1] (indices 0‑1). 3. For s=3 (index 3), 3-2=1 found once → subarray [1,1] (indices 1‑2). 4. For s=4 (index 4), 4-2=2 found once → subarray [1,1] (indices 2‑3). 5. Total count = 3.
Input
nums = [3, -1, 4, -2, 2], k = 3
Output
3
Explanation: 1. Prefix sums: [0, 3, 2, 6, 4, 6]. 2. s=3 (index 1): 3-3=0 found → subarray [3] (0‑0). 3. s=6 (index 3): 6-3=3 found once → subarray [-1,4] (1‑2). 4. s=6 (index 5): 6-3=3 found once → subarray [-1,4,-2,2] (1‑4). 5. Total count = 3.
Input
nums = [-2, 5, -1, 2, -2], k = 3
Output
1
Explanation: 1. Prefix sums: [0, -2, 3, 2, 4, 2]. 2. s=3 (index 2): 3-3=0 found → subarray [-2,5] (0‑1). 3. No other prefix sum yields a difference of 3. 4. Total count = 1.
Constraints
- 1 <= n <= 100000
- -1000000000 <= nums[i] <= 1000000000
- -100000000000000 <= K <= 100000000000000
- The sum of absolute values of all elements does not exceed 100000000000000
- All input values fit within 64‑bit signed integers
Optimal Approach & Strategy
Use a hash map to store the frequency of prefix sums encountered so far. For each current prefix sum, check if (currentPrefixSum - K) exists in the map and add its frequency to the count. This reduces the time complexity to O(n).
Brute Force Approach
Iterate through all possible start and end indices of subarrays, calculate the sum for each subarray, and count those that equal K. This results in O(n^2) time complexity.
Verified Code Solutions
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let idx = 0;
const n = input[idx++];
const nums = input.slice(idx, idx + n);
idx += n;
const k = input[idx];
const freq = new Map();
freq.set(0, 1);
let sum = 0;
let count = 0;
for (const num of nums) {
sum += num;
const need = sum - k;
if (freq.has(need)) count += freq.get(need);
freq.set(sum, (freq.get(sum) || 0) + 1);
}
console.log(count.toString());#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
vector<long long> nums(n);
for (int i = 0; i < n; ++i) cin >> nums[i];
long long k;
cin >> k;
unordered_map<long long, long long> freq;
freq[0] = 1;
long long sum = 0, count = 0;
for (long long num : nums) {
sum += num;
if (freq.find(sum - k) != freq.end())
count += freq[sum - k];
freq[sum]++;
}
cout << count << "\n";
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int[] nums = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(st.nextToken());
}
int k = Integer.parseInt(br.readLine().trim());
Map<Long, Long> freq = new HashMap<>();
freq.put(0L, 1L);
long sum = 0;
long count = 0;
for (int num : nums) {
sum += num;
long need = sum - k;
count += freq.getOrDefault(need, 0L);
freq.put(sum, freq.getOrDefault(sum, 0L) + 1);
}
System.out.println(count);
}
}
import sys
data = sys.stdin.read().strip().split()
if not data:
sys.exit()
idx = 0
n = int(data[idx]); idx += 1
nums = list(map(int, data[idx:idx + n])); idx += n
k = int(data[idx])
from collections import defaultdict
freq = defaultdict(int)
freq[0] = 1
sum_ = 0
count = 0
for num in nums:
sum_ += num
count += freq[sum_ - k]
freq[sum_] += 1
print(count)
const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let idx = 0;
const n = input[idx++];
const nums = input.slice(idx, idx + n);
idx += n;
const k = input[idx];
const freq = new Map();
freq.set(0, 1);
let sum = 0;
let count = 0;
for (const num of nums) {
sum += num;
const need = sum - k;
if (freq.has(need)) count += freq.get(need);
freq.set(sum, (freq.get(sum) || 0) + 1);
}
console.log(count.toString());
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.