Subarray Sum Equals K solution and explanation
IBM
Infosys
9 more videos on this problem
Count Subarray sum Equals K | Brute - Better -Optimaltake U forward · 24:09 · 824K views
Subarray Sum Equals K - Prefix Sums - Leetcode 560 - PythonNeetCode · 15:19 · 399K views
Subarray sum equals K | Number of subarrays with sum equals K | Leetcode #560Techdose · 15:44 · 208K views
LeetCode Subarray Sum Equals K Solution Explained - JavaNick White · 10:08 · 104K views
Number of Submatrices That Sum to Target | Subarray Sum Equals K | Leetcode 1074 | Leetcode 560codestorywithMIK · 56:53 · 47K views
LeetCode Day 22 - Subarray Sum Equals KErrichto Algorithms · 4:15 · 41K views
Subarray Sum Equals K (LeetCode 560) | Interview Essential | Prefix SumNikhil Lohia · 17:57 · 36K views
Subarray Sum Equals K - LeetCode 560 - Coding Interview QuestionsOne Code Man · 10:38 · 15K views
SUBARRAY SUM EQUALS K | LEETCODE 560 | PYTHON SOLUTIONCracking FAANG · 16:32 · 10K views
Subarray Sum Equals K | Prefix Sums | Leetcode 560 | Animation | IntuitionShreyaans Jain · 4:34 · 7K views
The problem
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,1,1], k = 2 Output: 2
Example 2:
Input: nums = [1,2,3], k = 3 Output: 2
Constraints:
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
Approach overview
Problem Overview: Given an integer array nums and an integer k, count how many continuous subarrays sum exactly to k. The array can contain negative numbers, so sliding window techniques do not work reliably. You need a method that checks every possible subarray sum efficiently.
Approach 1: Brute Force with Running Sum (O(n²) time, O(1) space)
Iterate over every possible starting index of a subarray. From each start position, extend the subarray to the right while maintaining a running sum. Each time the running sum equals k, increment the count. This avoids recomputing sums from scratch but still checks all O(n²) subarrays. The approach relies only on simple iteration over the array, so space usage remains constant.
This method is straightforward and useful when explaining the problem during an interview. It clearly shows how subarrays are formed and evaluated. However, it becomes slow for large inputs because every start index expands across the remaining array.
Approach 2: Prefix Sum with HashMap (O(n) time, O(n) space)
The optimal approach uses a running prefix sum combined with a frequency map. As you iterate through the array, maintain the cumulative sum up to the current index. If the current prefix sum is curr, then any earlier prefix sum equal to curr - k forms a subarray ending at the current index with sum k. Store counts of prefix sums in a hash table so each lookup runs in O(1).
Initialize the map with {0:1} to handle cases where the subarray starting at index 0 equals k. For each element, update the running sum, check how many times curr - k has appeared, and add that to the result. Then update the frequency of the current prefix sum in the map. This transforms the nested loop into a single linear pass through the array.
Recommended for interviews: Interviewers expect the prefix sum + hash map solution because it reduces the problem from O(n²) to O(n). Starting with the brute force explanation shows you understand the problem space. Moving to prefix sums demonstrates algorithmic optimization and familiarity with hash-based counting patterns that appear in many array problems.
Approach 1: Approach 1: Brute Force
This straightforward approach involves checking all possible subarrays in the given array. We calculate the sum for each subarray and check if it equals k. Although simple, it can be inefficient for large arrays due to its O(n^2) time complexity.
def subarray_sum(nums, k):
count = 0
for start in range(len(nums)):
total = 0
for end in range(start, len(nums)):
total += nums[end]
if total == k:
count += 1
return count
# Example usage
nums = [1, 1, 1]
k = 2
print(subarray_sum(nums, k))public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0;
for (int start = 0; start < nums.length; start++) {
int sum = 0;
for (int end = start; end < nums.length; end++) {
sum += nums[end];
if (sum == k) count++;
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 1, 1};
int k = 2;
System.out.println(sol.subarraySum(nums, k));
}
}#include <iostream>
#include <vector>
int subarraySum(std::vector<int>& nums, int k) {
int count = 0;
for (size_t start = 0; start < nums.size(); ++start) {
int sum = 0;
for (size_t end = start; end < nums.size(); ++end) {
sum += nums[end];
if (sum == k) ++count;
}
}
return count;
}
int main() {
std::vector<int> nums = {1, 1, 1};
int k = 2;
std::cout << subarraySum(nums, k) << std::endl;
return 0;
}function subarraySum(nums, k) {
let count = 0;
for (let start = 0; start < nums.length; start++) {
let sum = 0;
for (let end = start; end < nums.length; end++) {
sum += nums[end];
if (sum === k) count++;
}
}
return count;
}
console.log(subarraySum([1, 1, 1], 2));#include <stdio.h>
int subarraySum(int* nums, int numsSize, int k) {
int count = 0;
for (int start = 0; start < numsSize; start++) {
int sum = 0;
for (int end = start; end < numsSize; end++) {
sum += nums[end];
if (sum == k) count++;
}
}
return count;
}
int main() {
int nums[] = {1, 1, 1};
int k = 2;
int size = sizeof(nums)/sizeof(nums[0]);
printf("%d\n", subarraySum(nums, size, k));
return 0;
}using System;
public class Solution {
public int SubarraySum(int[] nums, int k) {
int count = 0;
for (int start = 0; start < nums.Length; start++) {
int sum = 0;
for (int end = start; end < nums.Length; end++) {
sum += nums[end];
if (sum == k) count++;
}
}
return count;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {1, 1, 1};
int k = 2;
Console.WriteLine(sol.SubarraySum(nums, k));
}
}This Python solution adopts a two-loop system to find subarrays whose sums equal k. The outer loop sets the starting index, while the inner loop calculates the sum. This approach yields O(n^2) time complexity and O(1) space complexity.
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 2: Approach 2: Using HashMap for Prefix Sums
This optimized approach uses a hashmap to store prefix sums, facilitating the identification of subarrays with the desired sum in constant time. By keeping a count of prefix sums that have been seen, we can determine how many times a specific sum - k has appeared, suggesting that a subarray ending at the current position sums to k.
from collections import defaultdict
def subarray_sum(nums, k):
prefix_sum_count = defaultdict(int)
prefix_sum_count[0] = 1
count = sum_ = 0
for num in nums:
sum_ += num
count += prefix_sum_count[sum_ - k]
prefix_sum_count[sum_] += 1
return count
# Example usage
nums = [1, 1, 1]
k = 2
print(subarray_sum(nums, k))import java.util.HashMap;
public class Solution {
public int subarraySum(int[] nums, int k) {
HashMap<Integer, Integer> prefixSumCount = new HashMap<>();
prefixSumCount.put(0, 1);
int count = 0, sum = 0;
for (int num : nums) {
sum += num;
count += prefixSumCount.getOrDefault(sum - k, 0);
prefixSumCount.put(sum, prefixSumCount.getOrDefault(sum, 0) + 1);
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 1, 1};
int k = 2;
System.out.println(sol.subarraySum(nums, k));
}
}#include <iostream>
#include <vector>
#include <unordered_map>
int subarraySum(std::vector<int>& nums, int k) {
std::unordered_map<int, int> prefixSumCount;
prefixSumCount[0] = 1;
int count = 0, sum = 0;
for (int num : nums) {
sum += num;
count += prefixSumCount[sum - k];
prefixSumCount[sum]++;
}
return count;
}
int main() {
std::vector<int> nums = {1, 1, 1};
int k = 2;
std::cout << subarraySum(nums, k) << std::endl;
return 0;
}function subarraySum(nums, k) {
const prefixSumCount = {0: 1};
let count = 0, sum = 0;
for (const num of nums) {
sum += num;
if (prefixSumCount[sum - k]) {
count += prefixSumCount[sum - k];
}
prefixSumCount[sum] = (prefixSumCount[sum] || 0) + 1;
}
return count;
}
console.log(subarraySum([1, 1, 1], 2));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int subarraySum(int* nums, int numsSize, int k) {
int count = 0, sum = 0, i;
int *prefixSumCount = calloc(20000, sizeof(int));
int offset = 10000;
prefixSumCount[offset] = 1;
for (i = 0; i < numsSize; i++) {
sum += nums[i];
int target = sum - k;
count += prefixSumCount[target + offset];
prefixSumCount[sum + offset]++;
}
free(prefixSumCount);
return count;
}
int main() {
int nums[] = {1, 1, 1};
int k = 2;
int size = sizeof(nums)/sizeof(nums[0]);
printf("%d\n", subarraySum(nums, size, k));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int SubarraySum(int[] nums, int k) {
var prefixSumCount = new Dictionary<int, int>();
prefixSumCount[0] = 1;
int count = 0, sum = 0;
foreach (int num in nums) {
sum += num;
if (prefixSumCount.TryGetValue(sum - k, out int prefixSumOccurrences)) {
count += prefixSumOccurrences;
}
if (!prefixSumCount.ContainsKey(sum))
prefixSumCount[sum] = 0;
prefixSumCount[sum]++;
}
return count;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {1, 1, 1};
int k = 2;
Console.WriteLine(sol.SubarraySum(nums, k));
}
}This Python solution utilizes a defaultdict to store prefix sums counts, allowing for dynamic and efficient querying of existing sums and direct summation of subarray occurrences satisfying the sum condition. The time and space complexities are O(n).
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Hash Table + Prefix Sum
We define a hash table cnt to store the number of times the prefix sum of the array nums appears. Initially, we set the value of cnt[0] to 1, indicating that the prefix sum 0 appears once.
We traverse the array nums, calculate the prefix sum s, then add the value of cnt[s - k] to the answer, and increase the value of cnt[s] by 1.
After the traversal, we return the answer.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.
function subarraySum(nums: number[], k: number): number {
const cnt: Map<number, number> = new Map();
cnt.set(0, 1);
let [ans, s] = [0, 0];
for (const x of nums) {
s += x;
ans += cnt.get(s - k) || 0;
cnt.set(s, (cnt.get(s) || 0) + 1);
}
return ans;
}func subarraySum(nums []int, k int) (ans int) {
cnt := map[int]int{0: 1}
s := 0
for _, x := range nums {
s += x
ans += cnt[s-k]
cnt[s]++
}
return
}use std::collections::HashMap;
impl Solution {
pub fn subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
let mut cnt = HashMap::new();
cnt.insert(0, 1);
let mut ans = 0;
let mut s = 0;
for &x in &nums {
s += x;
if let Some(&v) = cnt.get(&(s - k)) {
ans += v;
}
*cnt.entry(s).or_insert(0) += 1;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force | Time Complexity: O(n^2) |
| Approach 2: Using HashMap for Prefix Sums | Time Complexity: O(n) |
| Hash Table + Prefix Sum | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Running Sum | O(n²) | O(1) | Good for understanding subarray enumeration or when constraints are very small |
| Prefix Sum with HashMap | O(n) | O(n) | General case and expected interview solution for arrays with positive and negative numbers |
Frequently asked questions
Is Subarray Sum Equals K easy or hard?
Subarray Sum Equals K is classified as a Medium difficulty problem. The brute force solution is simple, but recognizing the prefix sum + hash map optimization requires familiarity with cumulative sum patterns and frequency counting techniques.
Subarray Sum Equals K Python/Java solution
Python and Java implementations both follow the same prefix sum + hash map logic. Maintain a running sum, check map.get(sum - k) to count valid subarrays, and update the map with the current prefix sum frequency. The algorithm runs in O(n) time regardless of language.
How to solve Subarray Sum Equals K in O(n)?
Maintain a running prefix sum while iterating through the array. Store the frequency of every prefix sum in a hash map. For each element, check if prefixSum - k exists in the map; its frequency tells how many subarrays ending at the current index sum to k. Update the map with the current prefix sum after each step.
What is the best approach for Subarray Sum Equals K?
The most efficient approach uses prefix sums with a hash map. As you scan the array, keep a running prefix sum and store how many times each sum appears. If the current sum is curr, any earlier prefix equal to curr - k forms a valid subarray. This method runs in O(n) time with O(n) extra space.
Is Subarray Sum Equals K asked at Google/Amazon/Meta?
Subarray Sum Equals K is a common interview question at companies like Amazon, Google, and Meta because it tests prefix sum reasoning and hash map usage. Variants of this pattern also appear in many array and counting problems during coding interviews.
What data structure is used in Subarray Sum Equals K?
The optimal solution uses a hash map (or dictionary) to store frequencies of prefix sums. Combined with a running prefix sum variable, this allows constant-time lookups to determine whether a previous prefix sum creates a subarray equal to k.
What is the time complexity of Subarray Sum Equals K?
The optimal solution runs in O(n) time using a prefix sum and hash map. Each element is processed once, and hash lookups occur in constant time. A brute force approach that checks all subarrays takes O(n²) time.