Log inSign up
mediumLeetCodeNot Started

Maximum Size 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 integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Example 1 · Standard Array with Negative Values:

Input: nums = [1, -1, 5, -2, 3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and has length 4.

Example 2 · Multiple Valid Subarrays:

Input: nums = [-2, -1, 2, 1], k = 1
Output: 2
Explanation: The subarray [-1, 2] sums to 1 and has length 2.

Example 3 · No Subarray Sums to K:

Input: nums = [1, 2, 3], k = 10
Output: 0
Explanation: No subarray sums to 10, so return 0.

Constraints:

  • 1 <= nums.length <= 2 * 105
  • -104 <= nums[i] <= 104
  • -109 <= k <= 109

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Prefix sum algebraic relationship — sum(i..j) = prefix[j] - prefix[i-1]
  • Hash table O(1) average lookup
  • Subarray Sum Equals K (Counting vs Length Maximization)

What You'll Learn

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

  • Understand why negative numbers break sliding window and mandate prefix sum maps.
  • Master the earliest-index retention principle for maximizing subarray lengths.
  • Initialize map with {0: -1} for 0-indexed prefix alignment.

Pattern Recognition Trigger

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

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • Use Prefix Sum + Hash Map.
  • If map.containsKey(runningSum - k) -> maxLen = max(maxLen, i - map.get(runningSum - k)).
  • Only put runningSum into map if not already present (preserve earliest index).

Connected Patterns:

Subarray Sum Equals KContiguous Array (0s and 1s)Continuous Subarray Sum

1. Check All Subarrays (Brute Force)

Intuition

Run two nested loops: outer loop i from 0 to n-1, and inner loop j from i to n-1. Accumulate elements in nums[i..j]. When the running sum equals k, compute length j - i + 1 and update maxLen.

When to apply: Use for small arrays to understand the problem constraints before introducing hash tables.

All Subarrays Sum (O(N^2) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Single element does not equal target 3
Visual state
Values and pointers at this exact step
pointers
S
1
-1
5
-2
3
0
↑ i=j
1
2
3
4
Variables at this step
start
0
end
0
currentSum
1
maxLen
0
Check / comparison
Subarray [0..0]: sum = 1 != 3
Decision / next transition
Not equal to k. Extend j.
Why this step matters

Single element does not equal target 3.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1public class Main {
2 public static class Solution {
3 public int maxSubArrayLen(int[] nums, int k) {
4 int n = nums.length;
5 int maxLen = 0;
6 for (int i = 0; i < n; i++) {
7 long sum = 0;
8 for (int j = i; j < n; j++) {
9 sum += nums[j];
10 if (sum == k) {
11 maxLen = Math.max(maxLen, j - i + 1);
12 }
13 }
14 }
15 return maxLen;
16 }
17 }
18
19 public static void main(String[] args) {
20 Solution sol = new Solution();
21 int[] nums = {1, -1, 5, -2, 3};
22 int k = 3;
23 System.out.println("Max Subarray Length: " + sol.maxSubArrayLen(nums, k));
24 }
25}

Time & Space Complexity

  • Time complexity: O(n^2) — Two nested loops exploring all pairs (i, j) take O(n2) operations.
  • Space complexity: O(1) — Only constant extra variables are used.

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 + Linear Scan (Better)

Intuition

Compute prefix array where prefix[i] is the sum of nums[0..i-1]. Then any subarray sum from i to j is prefix[j+1] - prefix[i]. We check all pairs in O(n2) without repeated inner summations.

When to apply: Use to illustrate the bridge between brute force and the hash map approach.

Prefix Sum Array + Difference Scan (O(N^2) Time, O(N) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Constant time range query
Visual state
Values and pointers at this exact step
pointers
S
0
1
0
5
3
6
0
↑ P
1
2
3
4
5
Variables at this step
prefix
[0,1,0,5,3,6]
maxLen
0
Check / comparison
Build prefix array: P = [0, 1, 0, 5, 3, 6]
Decision / next transition
Range sum nums[i..j] = P[j+1] - P[i].
Why this step matters

Constant time range query.

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

Time & Space Complexity

  • Time complexity: O(n^2) — Precomputing prefix array takes O(n) time, and checking pairs takes O(n2).
  • Space complexity: O(n) — O(n) auxiliary memory for the prefix array of size n + 1.

3. Prefix Sum + First-Occurrence Hash Map (Optimal)

Intuition

1. Maintain a running sum. 2. A subarray ending at index i has sum k if sum - k was seen at some previous index j; the subarray length is i - j. 3. To maximize length i - j, we want the earliest possible index j for that prefix sum. Therefore, we only insert a prefix sum into the map on its FIRST occurrence and never overwrite it. Initialize map with {0: -1}.

When to apply: Use as the optimal O(n) time and O(n) space solution for longest subarray with target sum.

Prefix Sum + Earliest-Index Hash Map (O(N) Time, O(N) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Earliest map stores only the first occurrence of each prefix sum to maximize length
Visual state
Values and pointers at this exact step
pointers
S
1
-1
5
-2
3
0
↑ init
1
2
3
4
Variables at this step
runningSum
0
maxLen
0
earliestMap
{"0":-1}
Check / comparison
Initialize earliestMap with base case: { 0: -1 }. Running sum = 0, maxLen = 0
Decision / next transition
Base case 0: -1 accounts for valid subarrays starting at index 0.
Why this step matters

Earliest map stores only the first occurrence of each prefix sum to maximize length.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.HashMap;
2import java.util.Map;
3
4public class Main {
5 public static class Solution {
6 public int maxSubArrayLen(int[] nums, int k) {
7 Map<Long, Integer> map = new HashMap<>();
8 map.put(0L, -1);
9 long sum = 0;
10 int maxLen = 0;
11 for (int i = 0; i < nums.length; i++) {
12 sum += nums[i];
13 if (map.containsKey(sum - k)) {
14 maxLen = Math.max(maxLen, i - map.get(sum - k));
15 }
16 if (!map.containsKey(sum)) {
17 map.put(sum, i);
18 }
19 }
20 return maxLen;
21 }
22 }
23
24 public static void main(String[] args) {
25 Solution sol = new Solution();
26 int[] nums = {1, -1, 5, -2, 3};
27 int k = 3;
28 System.out.println("Max Subarray Length: " + sol.maxSubArrayLen(nums, k));
29 }
30}

Time & Space Complexity

  • Time complexity: O(n) — A single pass through the array with O(1) average hash table operations takes O(n) time.
  • Space complexity: O(n) — The hash table stores at most n + 1 unique prefix sum entries.

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute ForceO(N^2)O(1)Check every subarray (i, j), compute sum, maximize length when sum == k.Evaluating all N2 subarrays.
2.Better — Prefix Array with Linear LookupO(N^2)O(N)Precompute prefix sum array and query ranges.Iterating through all index pairs.
3.Optimal — Prefix Sum + Earliest Index Hash MapOptimalO(N)O(N)Store earliest occurrence of each prefix sum in a hash map.None; industry-standard optimal solution.

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:

  • Subarray starting at index 0: {0: -1} ensures length is i - (-1) = i + 1.
  • Array with all negative numbers: e.g. [-2, -1, -3], k = -3 -> [-1, -2] or [-3] returns 2.
  • No valid subarray: returns 0.

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 Maximum Size Subarray Sum Equals k?

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

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

Back to DSA Sheet