Maximum Size Subarray Sum Equals k solution and explanation
Google
9 more videos on this problem
325. Maximum Size Subarray Sum Equals kAlGoreRhythms · 15:14 · 17K views
LeetCode 325. Maximum Size Subarray Sum Equals kHappy Coding · 15:51 · 6K views
LeetCode 325. Maximum Size Subarray Sum Equals k EP2happygirlzt · 6:20 · 5K views
Leetcode 325. Maximum Size Subarray Sum Equals kAlgorithms Casts · 14:11 · 1K views
325. Maximum Size Subarray Sum Equals k - Week 3/5 Leetcode April ChallengeProgramming Live with Larry · 7:05 · 462 views
Maximum Size SubArray Sum Equals K | Leetcode 325Debstuti Das · 15:29 · 443 views
Leetcode 325DailyLeetcode · 9:42 · 376 views
LeetCode 325. Maximum Size Subarray Sum Equals k | HashMap | Prefix Sum | JavaHow we live in Texas · 5:20 · 319 views
Amazon Interview Question - Maximum Size Subarray Sum Equals K - Leetcode #325 | Interview Helpinterviewhelp.io · 20:27 · 196 views
Leetcode 325 Maximum Size Subarray Sum Equals kDev_God · 6:47 · 182 views
The problem
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.
class Solution:
def maxSubArrayLen(self, nums: List[int], k: int) -> int:
d = {0: -1}
ans = s = 0
for i, x in enumerate(nums):
s += x
if s - k in d:
ans = max(ans, i - d[s - k])
if s not in d:
d[s] = i
return ansclass Solution {
public int maxSubArrayLen(int[] nums, int k) {
Map<Long, Integer> d = new HashMap<>();
d.put(0L, -1);
int ans = 0;
long s = 0;
for (int i = 0; i < nums.length; ++i) {
s += nums[i];
ans = Math.max(ans, i - d.getOrDefault(s - k, i));
d.putIfAbsent(s, i);
}
return ans;
}
}class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
unordered_map<long long, int> d{{0, -1}};
int ans = 0;
long long s = 0;
for (int i = 0; i < nums.size(); ++i) {
s += nums[i];
if (d.count(s - k)) {
ans = max(ans, i - d[s - k]);
}
if (!d.count(s)) {
d[s] = i;
}
}
return ans;
}
};/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maxSubArrayLen = function (nums, k) {
const d = new Map();
d.set(0, -1);
let ans = 0;
let s = 0;
for (let i = 0; i < nums.length; ++i) {
s += nums[i];
if (d.has(s - k)) {
ans = Math.max(ans, i - d.get(s - k));
}
if (!d.has(s)) {
d.set(s, i);
}
}
return ans;
};function maxSubArrayLen(nums: number[], k: number): number {
const d: Map<number, number> = new Map();
d.set(0, -1);
let ans = 0;
let s = 0;
for (let i = 0; i < nums.length; ++i) {
s += nums[i];
if (d.has(s - k)) {
ans = Math.max(ans, i - d.get(s - k)!);
}
if (!d.has(s)) {
d.set(s, i);
}
}
return ans;
}public class Solution {
public int MaxSubArrayLen(int[] nums, int k) {
var d = new Dictionary<int, int>();
d[0] = -1;
int ans = 0;
int s = 0;
for (int i = 0; i < nums.Length; i++) {
s += nums[i];
if (d.ContainsKey(s - k)) {
ans = Math.Max(ans, i - d[s - k]);
}
if (!d.ContainsKey(s)) {
d[s] = i;
}
}
return ans;
}
}func maxSubArrayLen(nums []int, k int) (ans int) {
d := map[int]int{0: -1}
s := 0
for i, x := range nums {
s += x
if j, ok := d[s-k]; ok && ans < i-j {
ans = i - j
}
if _, ok := d[s]; !ok {
d[s] = i
}
}
return
}use std::collections::HashMap;
impl Solution {
pub fn max_sub_array_len(nums: Vec<i32>, k: i32) -> i32 {
let mut d = HashMap::new();
d.insert(0, -1);
let mut ans = 0;
let mut s = 0;
for (i, &x) in nums.iter().enumerate() {
s += x;
if let Some(&j) = d.get(&(s - k)) {
ans = ans.max((i as i32) - j);
}
d.entry(s).or_insert(i as i32);
}
ans
}
}Complexity analysis
| 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 |
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.