Watch 10 video solutions for Maximum Size Subarray Sum Equals k, a medium level problem involving Array, Hash Table, Prefix Sum. This walkthrough by take U forward has 891,754 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 109Problem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Useful for understanding the problem or when input size is very small |
| Prefix Sum + Hash Table | O(n) | O(n) | Best general solution for arrays containing positive and negative numbers |