Skip to main content
Talentd

Maximum Size Subarray Sum Equals k - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TablePrefix Sum13 min readAsked at: Amazon, Microsoft, Goldman Sachs +5
Practice this problem

Problem Statement

Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there is not one, return 0 instead.

 

Example 1:

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

Example 2:

Input: nums = [-2,-1,2,1], k = 1
Output: 2
Explanation: The subarray [-1, 2] sums to 1 and is the longest.

 

Constraints:

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

Approach Overview

Problem Overview: You are given an integer array nums and an integer k. The task is to find the length of the longest contiguous subarray whose elements sum exactly to k. The array can contain positive, negative, and zero values, which rules out simple sliding window strategies.

Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)

Start each subarray at index i and extend it to every possible index j ≥ i. Maintain a running sum while expanding the subarray. Every time the running sum equals k, update the maximum length j - i + 1. This approach works because it checks every possible contiguous segment, but it requires two nested loops, leading to O(n²) time complexity. Space usage stays O(1) since only a few variables track the sum and best length.

The brute force solution helps confirm correctness and is sometimes acceptable when the input size is small. However, with arrays up to tens of thousands of elements, O(n²) quickly becomes too slow.

Approach 2: Prefix Sum + Hash Table (O(n) time, O(n) space)

The optimal solution relies on the idea of a prefix sum. Let prefix[i] represent the sum of elements from index 0 to i. If a subarray from i+1 to j sums to k, then:

prefix[j] - prefix[i] = k

Rearranging gives:

prefix[i] = prefix[j] - k

While iterating through the array, compute a running prefix sum. Use a hash table to store the earliest index where each prefix sum appears. For the current prefix sum curr, check whether curr - k exists in the map. If it does, a subarray ending at the current index sums to k. The length is the difference between the current index and the stored index.

Store each prefix sum in the map only the first time it appears. Keeping the earliest index ensures the longest possible subarray length. This algorithm processes each element once and performs constant-time hash lookups, resulting in O(n) time and O(n) space.

Recommended for interviews: Interviewers expect the prefix sum + hash table solution. Starting with the brute force method shows you understand the problem constraints. Transitioning to the O(n) prefix sum optimization demonstrates mastery of common array patterns and hash-based lookups used in many subarray problems.

Solution

We can use a hash table d to record the first occurrence index of each prefix sum in the array nums, initializing d[0] = -1. Additionally, we define a variable s to keep track of the current prefix sum.

Next, we iterate through the array nums. For the current number nums[i], we update the prefix sum s = s + nums[i]. If s - k exists in the hash table d, let j = d[s - k], then the length of the subarray that ends at nums[i] and satisfies the condition is i - j. We use a variable ans to maintain the length of the longest subarray that satisfies the condition. After that, if s does not exist in the hash table, we record s and its corresponding index i by setting d[s] = i. Otherwise, we do not update d[s]. It is important to note that there may be multiple positions i with the same value of s, so we only record the smallest i to ensure the subarray length is the longest.

After the iteration ends, we return ans.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n²)O(1)Useful for understanding the problem or when input size is very small
Prefix Sum + Hash TableO(n)O(n)Best general solution for arrays containing positive and negative numbers

Video Solution

325. Maximum Size Subarray Sum Equals k • AlGoreRhythms • 17,176 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Size Subarray Sum Equals k easy or hard?
The problem is classified as Medium difficulty. The brute force idea is straightforward, but identifying the prefix sum plus hash map optimization requires familiarity with common subarray sum patterns.
Maximum Size Subarray Sum Equals k Python/Java solution
Implement the prefix sum technique while storing sums in a dictionary (Python) or HashMap (Java). Track the earliest index for each prefix sum and update the maximum length whenever prefixSum - k is found in the map. The algorithm runs in O(n) time and O(n) space.
How to solve Maximum Size Subarray Sum Equals k in O(n)?
Maintain a running prefix sum while iterating through the array. Use a hash map to store the first index where each prefix sum occurs. For each element, check if prefixSum - k exists in the map. If it does, the distance between indices gives a subarray with sum k, allowing you to update the maximum length.
What is the best approach for Maximum Size Subarray Sum Equals k?
The most efficient approach uses prefix sums combined with a hash map. As you scan the array, store the earliest index for each prefix sum. If the current prefix sum minus k has appeared before, a valid subarray exists. This method runs in O(n) time with O(n) space.
Is Maximum Size Subarray Sum Equals k asked at Google/Amazon/Meta?
This problem appears frequently in technical interviews at companies like Amazon, Google, and Meta because it tests understanding of prefix sums, hash maps, and subarray patterns. Variants of this question also appear in system-level interview rounds.
What data structure is used in Maximum Size Subarray Sum Equals k?
The key data structure is a hash table (hash map) that stores prefix sums and their earliest indices. This enables constant-time lookups to determine whether a previous prefix sum can form a subarray with total sum k.
What is the time complexity of Maximum Size Subarray Sum Equals k?
The optimal prefix sum and hash map solution runs in O(n) time because the array is traversed once and each lookup in the hash table is O(1) on average. The brute force approach requires checking every subarray, which results in O(n²) time.

Ready to solve this problem?

Practice Maximum Size Subarray Sum Equals k with our built-in code editor and test cases.

Practice on FleetCode
Previous

Contiguous Array

Next

Maximum Beauty of an Array After Applying Operation