Log inSign up
mediumLeetCodeNot Started

Subarray Sum Equals K

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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 · Standard Array:

Input: nums = [1, 1, 1], k = 2
Output: 2
Explanation: The subarrays [1, 1] (indices 0..1) and [1, 1] (indices 1..2) both sum to 2.

Example 2 · Array with Non-consecutive 1s:

Input: nums = [1, 2, 3], k = 3
Output: 2
Explanation: Subarrays [1, 2] (sum 3) and [3] (sum 3) both sum to 3.

Example 3 · Array with Negative Numbers and Zeros:

Input: nums = [1, -1, 0], k = 0
Output: 3
Explanation: The matching subarrays are [1, -1], [0], and [1, -1, 0].

Constraints:

  • 1 <= nums.length <= 2 * 104
  • -1000 <= nums[i] <= 1000
  • -107 <= k <= 107

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Prefix sum algebraic identities — Sum(i, j) = Prefix(j) - Prefix(i-1)
  • Hash map frequency counting and O(1) average lookup
  • Understanding why Two Pointers fails when arrays contain negative numbers

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Derive the prefix subtraction complement formula: needed = currentSum - k.
  • Understand why the base case map[0] = 1 is mandatory.
  • Contrast hash-map prefix counting with two-pointer sliding window constraints.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Counting subarrays with a specific target sum k.
  • Array contains negative numbers or zeros (which invalidates sliding window).
  • Need an O(N) linear time solution with O(1) lookup per step.

Algorithmic Decision Tree:

  • When counting subarrays with sum = K and negative numbers are possible: Maintain running prefix sum and query hash map for (currentSum - k).

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Nested Loops All Subarrays

Intuition

Iterate through all possible subarrays (i..j), compute their sum, and increment count if sum == k.

Algorithm

  1. 1. Initialize count = 0.
  2. 2. For i from 0 to n-1: - currentSum = 0 - For j from i to n-1: - currentSum += nums[j] - If currentSum == k: count++.
  3. 3. Return count.

Brute Force All Subarrays Sum Calculation

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, -2, 1]
Current operationSTEP 1 OF 6
Phase 1 — MATCH 1 FOUND
Visual state
Values and pointers at this exact step
array
S
1
2
3
-2
1
0
↑ i=0
1
↑ j=1
2
3
4
Variables at this step
Subarray
[1, 2]
Sum
3
k
3
Count
1
Check / comparison
Subarray [1, 2]: sum = 1 + 2 = 3 == k (3).
Decision / next transition
MATCH 1 FOUND! count = 1.
Why this step matters

Phase 1 — MATCH 1 FOUND! count = 1: Subarray [0..1]: Elements [1, 2] sum to 3. Count increments to 1.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int subarraySum(int[] nums, int k) {
6 int count = 0;
7 for (int start = 0; start < nums.length; start++) {
8 int sum = 0;
9 for (int end = start; end < nums.length; end++) {
10 sum += nums[end];
11 if (sum == k) count++;
12 }
13 }
14 return count;
15 }
16 }
17
18 public static void main(String[] args) {
19 Solution sol = new Solution();
20 int[] nums = {1, 2, 3, -2, 1};
21 int k = 3;
22 System.out.println("Subarray count: " + sol.subarraySum(nums, k));
23 }
24}

Time & Space Complexity

  • Time complexity: O(N^2) — Evaluates all N*(N+1)/2 subarrays in O(N2) time.
  • Space complexity: O(1) — Auxiliary space is O(1).

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Prefix Sum Array with Pairwise Difference Check

Intuition

Precompute prefix sum array where prefix[i] is sum of first i elements, and check prefix[j] - prefix[i] == k.

Algorithm

  1. 1. Build prefix sum array of size n + 1: prefix[0] = 0, prefix[i] = prefix[i-1] + nums[i-1].
  2. 2. For i from 0 to n: - For j from i + 1 to n: - If prefix[j] - prefix[i] == k: count++.
  3. 3. Return count.

Cumulative Prefix Sum Array Scan Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 1, 3, 6, 4, 5]
Current operationSTEP 1 OF 6
Phase 1 — Subarray sum(ij) = prefix[j+1] - prefix[i]: Step 1 — Precompute Prefix: prefix = [0, 1, 3, 6, 4, 5] allows $O(1)$ range sum calculation
Visual state
Values and pointers at this exact step
array
S
0
1
3
6
4
5
0
↑ Prefix Array
1
2
3
4
5
Variables at this step
prefix
[0, 1, 3, 6, 4, 5]
Check / comparison
Precompute prefix sum array: prefix[i] = prefix[i-1] + nums[i-1].
Decision / next transition
Subarray sum(i..j) = prefix[j+1] - prefix[i].
Why this step matters

Phase 1 — Subarray sum(ij) = prefix[j+1] - prefix[i]: Step 1 — Precompute Prefix: prefix = [0, 1, 3, 6, 4, 5] allows O(1) range sum calculation.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int subarraySum(int[] nums, int k) {
6 int n = nums.length;
7 int[] prefix = new int[n + 1];
8 for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
9
10 int count = 0;
11 for (int start = 0; start < n; start++) {
12 for (int end = start + 1; end <= n; end++) {
13 if (prefix[end] - prefix[start] == k) count++;
14 }
15 }
16 return count;
17 }
18 }
19
20 public static void main(String[] args) {
21 Solution sol = new Solution();
22 int[] nums = {1, 2, 3, -2, 1};
23 int k = 3;
24 System.out.println("Subarray count: " + sol.subarraySum(nums, k));
25 }
26}

Time & Space Complexity

  • Time complexity: O(N^2) — Building prefix takes O(N) and checking all pairs takes O(N2).
  • Space complexity: O(N) — Requires auxiliary prefix array of size N + 1, consuming O(N) space.

3. Prefix Sum + Hash Map Frequency (Optimal & Standard)

Intuition

Maintain a running prefix sum and a Hash Map storing frequencies of seen prefix sums in O(N) linear time.

Algorithm

  1. 1. Initialize Hash Map prefixCounts = {0: 1}, currentSum = 0, count = 0.
  2. 2. For each num in nums: - currentSum += num - If (currentSum - k) is in prefixCounts: count += prefixCounts[currentSum - k] - prefixCounts[currentSum] = (prefixCounts[currentSum] || 0) + 1.
  3. 3. Return count.

Prefix Sum & Cumulative Frequency Map Trace

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [1, 2, 3, -2, 1]
Current operationSTEP 1 OF 7
Phase 1 — Base case: A prefix sum of 0 has occurred once: Step 1 — Base Case Setup: Map { 0: 1 } handles subarrays that sum to k starting right from index 0
Visual state
Values and pointers at this exact step
array
S
1
2
3
-2
1
0
↑ Init
1
2
3
4
Variables at this step
Running Sum
0
Map
{ 0: 1 }
Count
0
Check / comparison
Initialize map = { 0: 1 }, sum = 0, count = 0.
Decision / next transition
Base case: A prefix sum of 0 has occurred once.
Why this step matters

Phase 1 — Base case: A prefix sum of 0 has occurred once: Step 1 — Base Case Setup: Map { 0: 1 } handles subarrays that sum to k starting right from index 0.

Step 1 / 7
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int subarraySum(int[] nums, int k) {
6 int count = 0, currentSum = 0;
7 Map<Integer, Integer> map = new HashMap<>();
8 map.put(0, 1);
9
10 for (int num : nums) {
11 currentSum += num;
12 if (map.containsKey(currentSum - k)) {
13 count += map.get(currentSum - k);
14 }
15 map.put(currentSum, map.getOrDefault(currentSum, 0) + 1);
16 }
17 return count;
18 }
19 }
20
21 public static void main(String[] args) {
22 Solution sol = new Solution();
23 int[] nums = {1, 2, 3, -2, 1};
24 int k = 3;
25 System.out.println("Subarray count: " + sol.subarraySum(nums, k));
26 }
27}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass through array with O(1) average hash map lookups. Total time is O(N).
  • Space complexity: O(N) — Hash Map stores at most N+1 distinct prefix sums, consuming O(N) space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Approach 1: Nested Loops All SubarraysO(N^2)O(1)Iterate through all possible subarrays (i..j), compute their sum, and increment count if sum == k.Repeated redundant scans over the input.
2.Approach 2: Prefix Sum Array with Pairwise Difference CheckO(N^2)O(N)Precompute prefix sum array where prefix[i] is sum of first i elements, and check prefix[j] - prefix[i] == k.Auxiliary memory allocation or sorting step.
3.Approach 3: Prefix Sum + Hash Map Frequency (Optimal & Standard)OptimalO(N)O(N)Maintain a running prefix sum and a Hash Map storing frequencies of seen prefix sums in O(N) linear time.None. Asymptotically optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Array with Zeros [0, 0, 0], k = 0 — Input: `, Expected: ` —
  • Target K is Negative [1, -2, 1], k = -1 — Input: `, Expected: ` —
  • No Matching Subarray [1, 2, 3], k = 10 — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Subarray Sum Equals K?

2.Why is the brute force approach suboptimal for large inputs in Subarray Sum Equals K?

3.Which data structure or technique enables the optimal solution for Subarray Sum Equals K?

Back to DSA Sheet