Problem Informations

• Problem Index: 325
• Problem Link: Maximum Size Subarray Sum Equals k
• Topics: Array, Hash Table, Prefix Sum

Problem Description

Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there is not one, return 0 instead.

Example 1:

Input: nums = [1,-1,5,-2,3], k = 3  
Output: 4  
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

Example 2:

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

Constraints:

• $1 <= nums.length <= 2 \times 10^5$
• $-10^4 <= nums[i] <= 10^4$
• $-10^9 <= k <= 10^9$

Intuition

The problem requires finding the maximum length of a subarray that sums up to a given integer $k$. A straightforward approach would be to explore all possible subarrays and calculate their sums, but this would not be efficient due to the constraints involving large array sizes. Instead, a more efficient approach leverages the concept of prefix sums and hash maps to quickly identify subarrays that meet the criteria.

Approach

The solution makes use of a prefix sum technique in combination with a hash map to efficiently determine the maximum length of a subarray that sums to $k$. Here’s the step-by-step process:

1. Initialize Variables:

   • length: Store the size of the input array nums.
   • maxLength: Initialize this to 0 to keep track of the maximum length of the subarray found that sums to $k$.
   • prefixSum: Initialize this to 0 to maintain the cumulative sum of elements encountered so far.

2. Hash Map Setup:

   • Use a hash map prefixSumIndices to record the first occurrence of each prefix sum encountered. The map stores prefix sums as keys and their corresponding indices as values.
   • Insert the initial entry {0: -1} into the hash map. This acts as a base case to handle situations where a subarray starting from the beginning sums to $k$.

3. Iterate Through Array:

   • Iterate over each element in the array nums:
     • Update the prefixSum by adding the current element nums[i].
     • Check if there is a prefix sum that matches prefixSum - k. If it exists, it means there is a subarray from the next position of the found prefix sum to the current index i that sums to $k$.
     • Calculate the length of this subarray using i - prefixSumIndices[prefixSum - k] and update maxLength if the current subarray is longer than the previously found subarrays.
     • Register the first occurrence of the current prefixSum in the hash map prefixSumIndices if it hasn’t been already recorded.

4. Return Result:

   • After processing all elements, the value of maxLength will be the length of the longest subarray that sums to $k$. Return this value as the result.

Through this approach, we achieve a time complexity of $O(n)$, where $n$ is the length of the array nums, making it efficient even for large input sizes. The usage of a hash map ensures that we can quickly find the required prefix sum differences, while maintaining only the first occurrence of each prefix sum eliminates redundant calculations.

Code

C++

class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        int length = nums.size();
        int maxLength = 0;
        long long prefixSum = 0;
        
        // Hash map to store the first occurrence of each prefix sum
        unordered_map<long long, int> prefixSumIndices;
        prefixSumIndices[0] = -1;  // Initialize with prefix sum 0 at index -1
        
        for (int i = 0; i < length; i++) {
            prefixSum += nums[i];  // Update the running prefix sum

            // Check if there exists a subarray sum equals to k
            if (prefixSumIndices.find(prefixSum - k) != prefixSumIndices.end()) {
                // Update maxLength if this subarray is longer
                maxLength = max(maxLength, i - prefixSumIndices[prefixSum - k]);
            }
            
            // Record the first occurrence of the current prefix sum
            if (prefixSumIndices.find(prefixSum) == prefixSumIndices.end()) {
                prefixSumIndices[prefixSum] = i;
            }
        }
        
        return maxLength;
    }
};

Python

class Solution:
    def maxSubArrayLen(self, nums, k):
        length = len(nums)
        maxLength = 0
        prefixSum = 0

        # Hash map to store the first occurrence of each prefix sum
        prefixSumIndices = {}
        prefixSumIndices[0] = -1  # Initialize with prefix sum 0 at index -1

        for i in range(length):
            prefixSum += nums[i]  # Update the running prefix sum

            # Check if there exists a subarray sum equals to k
            if prefixSum - k in prefixSumIndices:
                # Update maxLength if this subarray is longer
                maxLength = max(maxLength, i - prefixSumIndices[prefixSum - k])

            # Record the first occurrence of the current prefix sum
            if prefixSum not in prefixSumIndices:
                prefixSumIndices[prefixSum] = i

        return maxLength

Complexity

• Time complexity: $O(n)$
  The algorithm involves iterating through the array nums once, which consists of $n$ elements. During each iteration, operations such as updating the prefix sum and checking/adding entries in the hash map take average constant time $O(1)$. Therefore, the overall time complexity is $O(n)$.

• Space complexity: $O(n)$
  A hash map is used to store prefix sums, where each prefix sum is associated with its index in the array. In the worst case, all elements contribute a unique prefix sum, resulting in $n$ entries stored in the hash map. Thus, the space complexity is $O(n)$.