Problem of The Day: Maximum Size Subarray Equals k

Problem Statement

leetcode problem link

Intuition

To solve the problem of finding the maximum length of a subarray that sums to a given value k, the initial thought is to use prefix sums to efficiently calculate the sum of any subarray. By keeping track of prefix sums and their earliest occurrences, we can quickly determine whether a subarray summing to k exists and track its length.

Approach

1. Calculate the prefix sum of the input array nums.
2. Use a dictionary seen to store the first occurrence index of each prefix sum.
3. Iterate through the array while:
   • Computing the prefix sum.
   • Checking if the current prefix sum equals k, which means the subarray from the start to the current index is a valid candidate.
   • Checking if (prefix sum - k) exists in seen, indicating a previous prefix sum that, if subtracted, gives the target k.
   • Updating the result with the maximum length found so far.
   • Recording the first occurrence of the current prefix sum to ensure the longest possible subarray is considered.

Complexity

• Time complexity:
  \(O(n)\)
  We traverse the array once to compute prefix sums and once more to evaluate subarray lengths, resulting in linear time.

• Space complexity:
  \(O(n)\)
  We use extra space to store the prefix sums and their indices in a dictionary.

Code

class Solution:
    def maxSubArrayLen(self, nums: List[int], k: int) -> int:
        start = 0
        N = len(nums)
        curr_sum = 0
        res = 0
        prefix = [0] * N
        seen = {}
        for i, num in enumerate(nums):
            curr_sum += num
            prefix[i] = curr_sum

        for i in range(N):
            val = prefix[i] - k
            if prefix[i] == k:
                res = max(res, i + 1)
            if val in seen:
                res = max(res, i - seen[val])
            if prefix[i] not in seen:  # to ensure the longest
                seen[prefix[i]] = i

        return res

Editorial Solution

Approach: Prefix Sum + Hash Map

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

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

            # Check if all of the numbers seen so far sum to k.
            if prefix_sum == k:
                longest_subarray = i + 1

            # If any subarray seen so far sums to k, then
            # update the length of the longest_subarray.
            if prefix_sum - k in indices:
                longest_subarray = max(longest_subarray, i - indices[prefix_sum - k])

            # Only add the current prefix_sum index pair to the
            # map if the prefix_sum is not already in the map.
            if prefix_sum not in indices:
                indices[prefix_sum] = i

        return longest_subarray