LeetCode 325: Maximum Size Subarray Sum Equals k Solution in Python – A Step-by-Step Guide

What Is LeetCode 325: Maximum Size Subarray Sum Equals k?

In LeetCode 325: Maximum Size Subarray Sum Equals k, you’re given an integer array nums and an integer k. Your task is to find the length of the longest contiguous subarray whose sum equals k. If no such subarray exists, return 0. For example, with nums = [1,-1,5,-2,3] and k = 3, the longest subarray is [1,-1,5,-2] (sum = 3), length 4. This problem tests your ability to track sums efficiently, connecting to concepts in LeetCode 560: Subarray Sum Equals K.

Problem Statement

• Input: An integer array nums and an integer k.
• Output: An integer—the length of the longest subarray with sum k, or 0 if none.
• Rules:
• Subarray must be contiguous.
• Sum must exactly equal k.
• Return 0 if no solution exists.

Constraints

• 1 <= nums.length <= 2 * 10⁵
• -10⁴ <= nums[i] <= 10⁴
• -10⁹ <= k <= 10⁹

Examples

• Input: nums = [1,-1,5,-2,3], k = 3
• Output: 4 (Subarray [1,-1,5,-2] sums to 3)
• Input: nums = [1,2,3], k = 4
• Output: 2 (Subarray [1,3] sums to 4)
• Input: nums = [1,2], k = 5
• Output: 0 (No subarray sums to 5)

Understanding the Problem: Finding the Longest Subarray

To solve LeetCode 325: Maximum Size Subarray Sum Equals k in Python, we need to find the longest contiguous subarray in nums with sum k. A naive approach—checking every subarray—is O(n²), too slow for up to 2 * 10⁵ elements. Instead, we’ll use:

• Best Solution (Hash Map with Prefix Sums): O(n) time, O(n) space—fast and elegant.
• Alternative Solution (Brute Force): O(n²) time, O(1) space—simple but inefficient.

Let’s start with the hash map solution, explained in a beginner-friendly way.

Best Solution: Hash Map with Prefix Sums

Why This Is the Best Solution

The hash map with prefix sums approach is the top choice for LeetCode 325 because it’s efficient—O(n) time, O(n) space—and cleverly uses cumulative sums to find subarrays in one pass. It tracks prefix sums in a hash map, leveraging the fact that a subarray sum equals k when the difference between two prefix sums matches k. It’s like keeping a running tally to spot the longest match—smart and quick!

How It Works

Think of this as a sum-tracking adventure:

• Step 1: Compute Prefix Sums:
• prefix_sum[i] = sum of elements from 0 to i.
• Step 2: Use Hash Map:
• Map stores prefix_sum → earliest index.
• For each position, check if prefix_sum - k exists; if so, length = current index - mapped index.
• Step 3: Update Max Length:
• Track the longest valid subarray.
• Step 4: Why It Works:
• If prefix_sum[j] - prefix_sum[i] = k, then subarray i+1 to j sums to k.
• Earliest index maximizes length.

It’s like finding treasure by tracking your steps!

Step-by-Step Example

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

• Prefix Sums: [1,0,5,3,6]
• Hash Map: {0:-1} (base case)
• Process:
• i=0, sum=1: 1-3=-2 (not in map), Map={0:-1, 1:0}
• i=1, sum=0: 0-3=-3 (not in map), Map={0:1, 1:0}
• i=2, sum=5: 5-3=2 (not in map), Map={0:1, 1:0, 5:2}
• i=3, sum=3: 3-3=0 (in map at 1), Length=3-(-1)=4, Map={0:1, 1:0, 5:2, 3:3}
• i=4, sum=6: 6-3=3 (in map at 3), Length=4-3=1
• Result: Max length = 4

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def maxSubArrayLen(self, nums: List[int], k: int) -> int:
        # Map to store prefix sum -> earliest index
        prefix_sums = {0: -1}  # Base case for subarray starting at 0
        curr_sum = 0
        max_len = 0

        # Traverse array
        for i in range(len(nums)):
            curr_sum += nums[i]
            # Check if subarray summing to k exists
            if curr_sum - k in prefix_sums:
                max_len = max(max_len, i - prefix_sums[curr_sum - k])
            # Only add if not seen (keep earliest index)
            if curr_sum not in prefix_sums:
                prefix_sums[curr_sum] = i

        return max_len

• Line 4: Initialize map with 0 at -1 (for subarrays from start).
• Lines 8-14: Process each element:
• Update running sum.
• Check if curr_sum - k exists; update max length.
• Store earliest occurrence of curr_sum.
• Time Complexity: O(n)—single pass.
• Space Complexity: O(n)—hash map.

This is like a sum-hunting detective—swift and sharp!

Alternative Solution: Brute Force

Why an Alternative Approach?

The brute-force approach—O(n²) time, O(1) space—checks every possible subarray by computing sums explicitly. It’s simpler to understand but impractical for large inputs, making it a good learning tool. It’s like searching every nook and cranny—thorough but slow!

How It Works

Check all subarrays:

• Step 1: For each start index:
• Compute running sum to each end index.
• Step 2: Track max length when sum equals k.

Step-by-Step Example

Example: nums = [1,2,3], k = 3

• Subarrays:
• [1]: 1
• [1,2]: 3 (Length 2)
• [1,2,3]: 6
• [2]: 2
• [2,3]: 5
• [3]: 3 (Length 1)
• Result: Max length = 2

Code for Brute Force Approach

Copy codeclass Solution:
    def maxSubArrayLen(self, nums: List[int], k: int) -> int:
        max_len = 0
        for i in range(len(nums)):
            curr_sum = 0
            for j in range(i, len(nums)):
                curr_sum += nums[j]
                if curr_sum == k:
                    max_len = max(max_len, j - i + 1)

        return max_len

• Time Complexity: O(n²)—nested loops.
• Space Complexity: O(1)—just variables.

It’s a sum-checking explorer—basic but heavy!

Comparing the Two Solutions

• Hash Map (Best):
• Pros: O(n) time, O(n) space, fast and scalable.
• Cons: Requires prefix sum insight.
• Brute Force (Alternative):
• Pros: O(n²) time, O(1) space, easy to follow.
• Cons: Too slow for large n.

Hash map wins hands down.

Additional Examples and Edge Cases

• [1], 1: 1.
• [-1,1], 0: 2.
• [1,2], 5: 0.

Both handle these well.

Complexity Breakdown

• Hash Map: Time O(n), Space O(n).
• Brute Force: Time O(n²), Space O(1).

Hash map is the clear choice.

Key Takeaways

• Hash Map: Prefix sums rule—efficient!
• Brute Force: Check all—simple!
• Python: Dicts and loops shine—see [Python Basics](/python/basics).
• Subarrays: Sums unlock lengths.

Final Thoughts: Find That Sum

LeetCode 325: Maximum Size Subarray Sum Equals k in Python is an array-sum adventure. The hash map solution offers speed and elegance, while brute force provides a baseline. Want more sum challenges? Try LeetCode 560: Subarray Sum Equals K or LeetCode 523: Continuous Subarray Sum. Ready to hunt? Head to Solve LeetCode 325 on LeetCode (premium) and measure that subarray today!