.png)
Subarray Sum Equals K
(Prefix Sum + Hashing)
Problem Statement
You are given an integer array arr and an integer k.
Your task is to find the total number of continuous subarrays whose sum equals k.
Example 1
Input
arr = [1,1,1]
k = 2
Output
2
Example 2
Input
arr = [1,2,3]
k = 3
Output
2
Why This Problem Is Important
- Very frequent interview question
- Introduces prefix sum + hashing
- Works with negative numbers (sliding window fails)
- Core foundation for advanced subarray problems
- Asked in FAANG & top product companies
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(n²) | O(1) |
| Approach 2 | Prefix Sum (No Hashing) | O(n²) | O(n) |
| Approach 3 | Prefix Sum + Hash Map (Optimal) | O(n) | O(n) |
Approach 1: Brute Force
Idea
Check all possible subarrays and calculate their sum.
Algorithm
- Initialize count = 0
- For each start index i
- Initialize sum = 0
- For each end index j ≥ i
- Add arr[j] to sum
- If sum == k, increment count
Time & Space Complexity
- Time: O(n²)
- Space: O(1)
C
#include
int main() {
int arr[] = {1,2,3};
int n = 3, k = 3, count = 0;
for(int i = 0; i < n; i++) {
int sum = 0;
for(int j = i; j < n; j++) {
sum += arr[j];
if(sum == k)
count++;
}
}
printf("%d", count);
return 0;
}
Output
2
C++
#include
using namespace std;
int main() {
int arr[] = {1,2,3};
int n = 3, k = 3, count = 0;
for(int i = 0; i < n; i++) {
int sum = 0;
for(int j = i; j < n; j++) {
sum += arr[j];
if(sum == k)
count++;
}
}
cout << count;
return 0;
}
Output
2
Java
public class SubarraySumK {
public static void main(String[] args) {
int[] arr = {1,2,3};
int k = 3, count = 0;
for(int i = 0; i < arr.length; i++) {
int sum = 0;
for(int j = i; j < arr.length; j++) {
sum += arr[j];
if(sum == k)
count++;
}
}
System.out.print(count);
}
}
Output
2
Python
arr = [1,2,3]
k = 3
count = 0
for i in range(len(arr)):
sum = 0
for j in range(i, len(arr)):
sum += arr[j]
if sum == k:
count += 1
print(count)
Output
2
JavaScript
let arr = [1,2,3];
let k = 3;
let count = 0;
for (let i = 0; i < arr.length; i++) {
let sum = 0;
for (let j = i; j < arr.length; j++) {
sum += arr[j];
if (sum === k)
count++;
}
}
console.log(count);
Output
2
C#
using System;
class Program {
static void Main() {
int[] arr = {1,2,3};
int k = 3, count = 0;
for(int i = 0; i < arr.Length; i++) {
int sum = 0;
for(int j = i; j < arr.Length; j++) {
sum += arr[j];
if(sum == k)
count++;
}
}
Console.WriteLine(count);
}
}
Output
2
Approach 2: Prefix Sum (Without Hashing)
Idea
Store prefix sums and check all pairs whose difference equals k.
Algorithm
- Build prefix sum array
- For all pairs (i, j)
- If prefix[j] - prefix[i] == k
- Increment count
Time & Space Complexity
- Time: O(n²)
- Space: O(n)0
C
#include
int main() {
int arr[] = {1,2,3};
int n = 3, k = 3, count = 0;
int prefix[3];
prefix[0] = arr[0];
for(int i = 1; i < n; i++)
prefix[i] = prefix[i-1] + arr[i];
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
int sum = prefix[j] - (i > 0 ? prefix[i-1] : 0);
if(sum == k)
count++;
}
}
printf("%d", count);
return 0;
}
Output
2
C++
#include
using namespace std;
int main() {
int arr[] = {1,2,3};
int n = 3, k = 3, count = 0;
int prefix[3];
prefix[0] = arr[0];
for(int i = 1; i < n; i++)
prefix[i] = prefix[i-1] + arr[i];
for(int i = 0; i < n; i++)
for(int j = i; j < n; j++) {
int sum = prefix[j] - (i > 0 ? prefix[i-1] : 0);
if(sum == k) count++;
}
cout << count;
return 0;
}
Output
2
Java
public class SubarraySumKPrefix {
public static void main(String[] args) {
int[] arr = {1,2,3};
int n = arr.length, k = 3, count = 0;
int[] prefix = new int[n];
prefix[0] = arr[0];
for(int i = 1; i < n; i++)
prefix[i] = prefix[i-1] + arr[i];
for(int i = 0; i < n; i++)
for(int j = i; j < n; j++) {
int sum = prefix[j] - (i > 0 ? prefix[i-1] : 0);
if(sum == k) count++;
}
System.out.println(count);
}
}
Output
2
Python
arr = [1,2,3]
k = 3
n = len(arr)
prefix = [0]*n
prefix[0] = arr[0]
for i in range(1, n):
prefix[i] = prefix[i-1] + arr[i]
count = 0
for i in range(n):
for j in range(i, n):
sum = prefix[j] - (prefix[i-1] if i > 0 else 0)
if sum == k:
count += 1
print(count)
Output
2
JavaScript
let arr = [1,2,3];
let k = 3;
let n = arr.length;
let count = 0;
let prefix = new Array(n);
prefix[0] = arr[0];
for (let i = 1; i < n; i++)
prefix[i] = prefix[i-1] + arr[i];
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
let sum = prefix[j] - (i > 0 ? prefix[i-1] : 0);
if (sum === k)
count++;
}
}
console.log(count);
Output
2
C#
using System;
class Program {
static void Main() {
int[] arr = {1,2,3};
int k = 3, count = 0;
int[] prefix = new int[arr.Length];
prefix[0] = arr[0];
for(int i = 1; i < arr.Length; i++)
prefix[i] = prefix[i - 1] + arr[i];
for(int i = 0; i < arr.Length; i++)
for(int j = i; j < arr.Length; j++) {
int sum = prefix[j] - (i > 0 ? prefix[i - 1] : 0);
if(sum == k) count++;
}
Console.WriteLine(count);
}
}
Output
2
Approach 3: Prefix Sum + Hash Map (Optimal)
Idea
If:
currentSum - k = previousSum
Then subarray sum equals k.
Algorithm
- Initialize map[0] = 1
- Traverse array:
- Add current element to sum
- If (sum - k) exists in map, add its frequency to count
- Increment frequency of sum
Time & Space Complexity
- Time: O(n)
- Space: O(n)
C
#include
int main() {
int arr[] = {1,2,3};
int n = 3, k = 3;
int sum = 0, count = 0;
int hash[1000] = {0};
hash[500] = 1; // offset for sum = 0
for(int i = 0; i < n; i++) {
sum += arr[i];
count += hash[sum - k + 500];
hash[sum + 500]++;
}
printf("%d", count);
return 0;
}
Output
2
C++
#include
#include
using namespace std;
int main() {
int arr[] = {1,2,3};
int k = 3, sum = 0, count = 0;
unordered_map mp;
mp[0] = 1;
for(int num : arr) {
sum += num;
count += mp[sum - k];
mp[sum]++;
}
cout << count;
return 0;
}
Output
2
Java
import java.util.HashMap;
public class SubarraySumK {
public static void main(String[] args) {
int[] arr = {1,2,3};
int k = 3, sum = 0, count = 0;
HashMap map = new HashMap<>();
map.put(0, 1);
for(int num : arr) {
sum += num;
count += map.getOrDefault(sum - k, 0);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
System.out.print(count);
}
}
Output
2
Python
arr = [1,2,3]
k = 3
sum = 0
count = 0
mp = {0: 1}
for num in arr:
sum += num
count += mp.get(sum - k, 0)
mp[sum] = mp.get(sum, 0) + 1
print(count)
Output
2
JavaScript
let arr = [1,2,3];
let k = 3;
let sum = 0, count = 0;
let map = new Map();
map.set(0, 1);
for (let num of arr) {
sum += num;
count += map.get(sum - k) || 0;
map.set(sum, (map.get(sum) || 0) + 1);
}
console.log(count);
Output
2
C#
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr = {1,2,3};
int k = 3, sum = 0, count = 0;
Dictionary map = new Dictionary();
map[0] = 1;
foreach(int num in arr) {
sum += num;
if(map.ContainsKey(sum - k))
count += map[sum - k];
if(map.ContainsKey(sum))
map[sum]++;
else
map[sum] = 1;
}
Console.WriteLine(count);
}
}
Output
2
Summary
- Brute force checks all subarrays
- Prefix sum improves clarity but still O(n²)
- Prefix sum + hashing is optimal and interview-preferred
- Handles negative numbers efficiently
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
