NUHMAN.com

Introduction

LeetCode 325: Maximum Size Subarray Sum Equals k is a classic prefix sum + hashmap problem. You're given an array of integers and a target sum k, and you're asked to find the length of the longest subarray that sums up to k.

This is a perfect example of how prefix sums can be used to solve subarray problems in O(n) time.

Problem Statement

Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k.

If no such subarray exists, return 0.

Example

python

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.

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

✅ Approach: Prefix Sum + HashMap

Step-by-Step Explanation

We use a running sum (prefix sum) and store the first occurrence of each prefix sum in a hashmap.

• Let’s say prefix_sum is the running total up to index i.
• If prefix_sum - k has been seen before at index j, then the subarray nums[j+1:i+1] has a sum of k.

Why it works?

Because prefix_sum[i] - prefix_sum[j] = k → subarray j+1 to i sums to k.

✅ Python Code

python

class Solution:
    def maxSubArrayLen(self, nums: list[int], k: int) -> int:
        prefix_sum = 0
        prefix_map = {}  # maps prefix_sum -> earliest index
        max_len = 0

        for i, num in enumerate(nums):
            prefix_sum += num

            if prefix_sum == k:
                max_len = i + 1

            if (prefix_sum - k) in prefix_map:
                max_len = max(max_len, i - prefix_map[prefix_sum - k])

            # Only store the earliest index for a given prefix sum
            if prefix_sum not in prefix_map:
                prefix_map[prefix_sum] = i

        return max_len

🧪 Dry Run Example

Input: nums = [1, -1, 5, -2, 3], k = 3

• Prefix sums: [1, 0, 5, 3, 6]
• At index 3 (value -2): prefix_sum = 3 → match found!
• Longest subarray so far is from index 0 to 3 → length 4

Output: 4

⏱️ Time & Space Complexity

MetricValueTime ComplexityO(n)Space ComplexityO(n)

🧠 Key Takeaways

• The hashmap tracks first occurrence of each prefix sum.
• If prefix_sum - k exists in map, it means a subarray ending at current index sums to k.
• Always store the earliest index to maximize subarray length.

❓ Edge Cases

• Empty array → return 0
• No subarray sums to k → return 0
• Multiple subarrays sum to k → return the longest

✅ Conclusion

LeetCode 325 teaches a powerful trick for subarray problems: prefix sums + hashmap. It helps reduce nested loops to a single pass. Once you grasp this pattern, many similar problems become much easier to handle.