LeetCode 325 - Maximum Size Subarray Sum Equals k

The problem asks us to find the longest contiguous subarray whose sum is exactly equal to a given integer k. A subarray is a continuous portion of the array. This means we cannot reorder elements or skip positions.

leetcodemediumarrayhash-tableprefix-sum

LeetCode Problem 325

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Prefix Sum

Solution

Problem Understanding

The problem asks us to find the longest contiguous subarray whose sum is exactly equal to a given integer k.

A subarray is a continuous portion of the array. This means we cannot reorder elements or skip positions. We must choose a start index and an end index such that every element between them is included.

The input consists of:

  • nums, an integer array that may contain positive numbers, negative numbers, and zeros
  • k, the target sum we want a subarray to equal

The output is a single integer representing the maximum possible length of any subarray whose elements sum to k. If no such subarray exists, we return 0.

The presence of negative numbers is extremely important. If the array only contained positive numbers, a sliding window technique would work because expanding the window would always increase the sum and shrinking it would always decrease the sum. However, negative values break that property. A window sum can increase or decrease unpredictably, so we need a different approach.

The constraints are large:

  • nums.length can be as large as 2 * 10^5
  • Values can be negative
  • k can also be very large or very small

These constraints strongly suggest that an O(n^2) solution will be too slow. With 200,000 elements, a quadratic approach would require tens of billions of operations in the worst case.

Some important edge cases include:

  • Arrays where no subarray sums to k
  • Arrays containing negative numbers
  • Arrays containing many zeros
  • Cases where the entire array sums to k
  • Cases where multiple subarrays sum to k, but only the longest should be returned
  • Cases where the optimal subarray starts at index 0

The problem guarantees that the array contains at least one element, so we never need to handle an empty input array.

Approaches

Brute Force Approach

The most direct solution is to examine every possible subarray.

For each starting index, we can expand the subarray one element at a time while maintaining the running sum. Whenever the running sum equals k, we compute the length of that subarray and update the maximum answer.

This works because every possible contiguous subarray is checked exactly once. Therefore, if a valid subarray exists, we will eventually find it.

However, there are O(n^2) possible subarrays. Even with incremental sum computation, the total runtime remains quadratic. Given the constraint of 2 * 10^5 elements, this approach is far too slow.

Optimal Approach, Prefix Sum + Hash Map

The key insight is that prefix sums allow us to compute subarray sums efficiently.

Suppose:

  • prefixSum[i] is the sum of elements from index 0 to i

Then the sum of a subarray from index j + 1 to i is:

$$\text{prefixSum}[i] - \text{prefixSum}[j]$$

We want this subarray sum to equal k, so:

$$\text{prefixSum}[i] - \text{prefixSum}[j] = k$$

Rearranging:

$$\text{prefixSum}[j] = \text{prefixSum}[i] - k$$

This means that while processing index i, if we have previously seen a prefix sum equal to currentPrefix - k, then the subarray between those two positions sums to k.

A hash map allows us to look up previous prefix sums in constant time.

An important optimization is that we store only the earliest occurrence of each prefix sum. Earlier indices produce longer subarrays, which is exactly what we want.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Checks every possible subarray
Optimal O(n) O(n) Uses prefix sums and a hash map for constant-time lookups

Algorithm Walkthrough

  1. Initialize a hash map that stores the earliest index where each prefix sum appears.

The reason we store the earliest index is that earlier occurrences create longer subarrays later. 2. Insert the pair {0: -1} into the hash map.

This handles cases where a valid subarray starts at index 0. If the running prefix sum itself becomes k, then currentPrefix - k equals 0, and the subarray length becomes i - (-1). 3. Initialize:

  • prefix_sum = 0
  • max_length = 0
  1. Iterate through the array from left to right.
  2. At each index:
  • Add the current number to prefix_sum
  1. Compute:
  • needed = prefix_sum - k

If needed exists in the hash map, then there is a previous prefix sum such that the subarray between those two indices sums to k. 7. Calculate the subarray length:

  • current_length = current_index - previous_index

Update max_length if this length is larger. 8. If the current prefix_sum has not been seen before, store it in the hash map with the current index.

We do not overwrite existing entries because the earliest occurrence gives the longest future subarray. 9. Continue until the array is fully processed. 10. Return max_length.

Why it works

The algorithm relies on the mathematical property of prefix sums:

$$\text{subarraySum}(j+1, i) = \text{prefixSum}[i] - \text{prefixSum}[j]$$

Whenever we find a previous prefix sum equal to currentPrefix - k, we know the elements between those positions sum to k.

By storing the earliest occurrence of every prefix sum, we guarantee that any matching subarray found is as long as possible for that ending position. Since we examine every index exactly once, the final answer is the maximum valid subarray length overall.

Python Solution

from typing import List

class Solution:
    def maxSubArrayLen(self, nums: List[int], k: int) -> int:
        prefix_to_index = {0: -1}

        prefix_sum = 0
        max_length = 0

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

            needed = prefix_sum - k

            if needed in prefix_to_index:
                current_length = index - prefix_to_index[needed]
                max_length = max(max_length, current_length)

            if prefix_sum not in prefix_to_index:
                prefix_to_index[prefix_sum] = index

        return max_length

The implementation begins by creating a dictionary called prefix_to_index. This maps each prefix sum to the earliest index where it appears.

The entry {0: -1} is critical. It allows the algorithm to correctly handle subarrays that begin at index 0.

As we iterate through the array, we continuously update prefix_sum. For each position, we compute needed = prefix_sum - k. If this value already exists in the hash map, then we have found a valid subarray ending at the current index.

The length of that subarray is calculated using the difference between indices.

We only store a prefix sum the first time it appears. This preserves the earliest occurrence, which maximizes future subarray lengths.

Finally, after processing all elements, we return the largest length found.

Go Solution

func maxSubArrayLen(nums []int, k int) int {
	prefixToIndex := map[int]int{
		0: -1,
	}

	prefixSum := 0
	maxLength := 0

	for index, num := range nums {
		prefixSum += num

		needed := prefixSum - k

		if previousIndex, exists := prefixToIndex[needed]; exists {
			currentLength := index - previousIndex

			if currentLength > maxLength {
				maxLength = currentLength
			}
		}

		if _, exists := prefixToIndex[prefixSum]; !exists {
			prefixToIndex[prefixSum] = index
		}
	}

	return maxLength
}

The Go implementation follows the exact same algorithmic structure as the Python version.

Go uses a map[int]int to store prefix sums and their earliest indices. The exists boolean from map lookups is used to safely determine whether a prefix sum has already appeared.

Integers in Go are large enough for the given constraints, so overflow is not a concern here.

Unlike Python dictionaries, Go maps require explicit existence checks before reading values.

Worked Examples

Example 1

Input:

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

Initial state:

prefix_to_index = {0: -1}
prefix_sum = 0
max_length = 0
Index Num Prefix Sum Needed (prefix_sum - k) Found? Subarray Length Max Length Hash Map
0 1 1 -2 No - 0 {0:-1, 1:0}
1 -1 0 -3 No - 0 {0:-1, 1:0}
2 5 5 2 No - 0 {0:-1, 1:0, 5:2}
3 -2 3 0 Yes 3 - (-1) = 4 4 {0:-1, 1:0, 5:2, 3:3}
4 3 6 3 Yes 4 - 3 = 1 4 {0:-1, 1:0, 5:2, 3:3, 6:4}

Final answer:

4

The longest subarray is:

[1, -1, 5, -2]

Example 2

Input:

nums = [-2, -1, 2, 1]
k = 1

Initial state:

prefix_to_index = {0: -1}
prefix_sum = 0
max_length = 0
Index Num Prefix Sum Needed (prefix_sum - k) Found? Subarray Length Max Length Hash Map
0 -2 -2 -3 No - 0 {0:-1, -2:0}
1 -1 -3 -4 No - 0 {0:-1, -2:0, -3:1}
2 2 -1 -2 Yes 2 - 0 = 2 2 {0:-1, -2:0, -3:1, -1:2}
3 1 0 -1 Yes 3 - 2 = 1 2 {0:-1, -2:0, -3:1, -1:2}

Final answer:

2

The longest subarray is:

[-1, 2]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed once with constant-time hash map operations
Space O(n) The hash map may store up to one prefix sum per index

The algorithm performs a single linear scan through the array. Every iteration performs only constant-time operations such as arithmetic, hash map lookups, and hash map insertions.

The extra space comes from storing prefix sums in the hash map. In the worst case, every prefix sum is unique, so the map grows to size n.

Test Cases

from typing import List

class Solution:
    def maxSubArrayLen(self, nums: List[int], k: int) -> int:
        prefix_to_index = {0: -1}

        prefix_sum = 0
        max_length = 0

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

            needed = prefix_sum - k

            if needed in prefix_to_index:
                current_length = index - prefix_to_index[needed]
                max_length = max(max_length, current_length)

            if prefix_sum not in prefix_to_index:
                prefix_to_index[prefix_sum] = index

        return max_length

solution = Solution()

assert solution.maxSubArrayLen([1, -1, 5, -2, 3], 3) == 4  # provided example 1
assert solution.maxSubArrayLen([-2, -1, 2, 1], 1) == 2  # provided example 2

assert solution.maxSubArrayLen([1, 2, 3], 6) == 3  # entire array sums to k
assert solution.maxSubArrayLen([1, 2, 3], 7) == 0  # no valid subarray
assert solution.maxSubArrayLen([0, 0, 0], 0) == 3  # all zeros
assert solution.maxSubArrayLen([5], 5) == 1  # single element equals k
assert solution.maxSubArrayLen([5], 1) == 0  # single element does not equal k
assert solution.maxSubArrayLen([-1, -1, 1], 0) == 2  # negative numbers
assert solution.maxSubArrayLen([1, -1, 1, -1, 1], 0) == 4  # repeated prefix sums
assert solution.maxSubArrayLen([3, 1, -1, 2, -2, 3], 3) == 5  # longest not first found
assert solution.maxSubArrayLen([1, 2, -2, 4, -4], 0) == 4  # zero-sum subarray
assert solution.maxSubArrayLen([10000] * 1000, 10000000) == 1000  # large uniform array
Test Why
[1, -1, 5, -2, 3], k=3 Validates the primary example
[-2, -1, 2, 1], k=1 Validates handling of negatives
[1,2,3], k=6 Entire array is the answer
[1,2,3], k=7 No valid subarray exists
[0,0,0], k=0 Multiple overlapping zero-sum subarrays
[5], k=5 Single-element success case
[5], k=1 Single-element failure case
[-1,-1,1], k=0 Negative values affect prefix sums
[1,-1,1,-1,1], k=0 Repeated prefix sums test correctness
[3,1,-1,2,-2,3], k=3 Longest subarray is not the first discovered
[1,2,-2,4,-4], k=0 Zero-sum subarray in the middle
Large repeated array Stress test for performance

Edge Cases

One important edge case occurs when the valid subarray starts at index 0. This is easy to mishandle if the implementation only looks for previous prefix sums in the hash map. The initialization {0: -1} solves this problem by pretending there is a prefix sum of zero before the array begins. When the running prefix sum becomes exactly k, the algorithm correctly computes the full length from the start of the array.

Another tricky case involves repeated prefix sums. For example, in [1, -1, 1, -1], the same prefix sum may appear multiple times. If we overwrite earlier indices in the hash map, we would lose the ability to form the longest possible subarray later. The implementation avoids this by storing only the first occurrence of each prefix sum.

Arrays containing negative numbers are also a major source of bugs. Many array-sum problems can be solved using sliding windows, but that technique fails here because the sum is not monotonic. Adding a negative value can decrease the sum unexpectedly. The prefix sum approach works correctly regardless of whether numbers are positive, negative, or zero.

A final important edge case is when no subarray sums to k. In that scenario, the algorithm never updates max_length, so it correctly returns 0.