LeetCode Solutions Blog

Maximum Size Subarray Sum Equals k

Number: 325

Difficulty: Medium

Paid? Yes

Problem Description

Given an integer array and an integer k, determine the maximum length of a contiguous subarray that sums to k. If no such subarray exists, return 0.

Key Insights

Utilize the prefix sum concept to convert subarray sum queries into differences between two prefix sums.
Use a hash table (dictionary/map) to store the earliest occurrence of each prefix sum.
For each index, check if (current_prefix_sum - k) exists in the hash table to identify a valid subarray.
Handling negative numbers correctly is crucial since prefix sums can decrease.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

Traverse the array while maintaining a cumulative (prefix) sum. For every index, calculate the current prefix sum and check if (current_prefix_sum - k) has been seen before in a hash map. If found, update the maximum subarray length with the difference between the current index and the stored index for (current_prefix_sum - k).
Store the prefix sums in a hash table only if they are seen for the first time to preserve the earliest index, which helps maximize the subarray length. This approach efficiently finds the longest subarray summing to k in a single pass.

Code Solutions

# Python solution with detailed comments
def maxSubArrayLen(nums, k):
    # Dictionary to store prefix sum and its earliest index
    prefix_sum_index = {}
    # Initialize with prefix sum 0 at index -1 to handle subarrays starting from index 0
    prefix_sum_index[0] = -1
    current_sum = 0
    max_length = 0

    # Iterate over the array
    for index, num in enumerate(nums):
        # Update the cumulative sum
        current_sum += num
        
        # If (current_sum - k) exists, we found a subarray summing to k
        if (current_sum - k) in prefix_sum_index:
            # Calculate subarray length and update maximum if longer
            max_length = max(max_length, index - prefix_sum_index[current_sum - k])
        
        # Record the prefix sum index if not seen before for maximizing subarray length
        if current_sum not in prefix_sum_index:
            prefix_sum_index[current_sum] = index

    return max_length

# Example usage:
print(maxSubArrayLen([1, -1, 5, -2, 3], 3))  # Output: 4