Maximum Size Subarray equals k

105.Maximum Size Subarray Sum Equals k

Array

Prefix Sum

Hash Table

Problem Statement:

Given an array of integers nums and an integer k, find the maximum length of a subarray that sums to k. If there isn't one, return 0.

Algorithm:

1. Use a prefix sum to track the cumulative sum of the array as you iterate through it.
2. Store the first occurrence of each prefix sum in a hash map. This ensures that we find the longest subarray.
3. For each element in the array:
   • Calculate the current prefix sum.
   • Check if sum - k exists in the hash map:
     • If it does, calculate the subarray length and update the maximum length.
   • Store the current prefix sum in the hash map if it's not already present.
4. Return the maximum length found.

Complexity:

Time: O(n), where n is the length of the array | Space: O(n).

Java Implementation:

// Max subarray of length k
public int maxSubArrayLen(int[] nums, int k) {
    int sum = 0;
    Map preSum = new HashMap<>();
    int max = 0;

    // Initialize with prefix sum of 0 at index -1
    preSum.put(0, -1);

    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];

        // Check if there exists a subarray sum equals to k
        if (preSum.containsKey(sum - k)) {
            max = Math.max(max, i - preSum.get(sum - k));
        }

        // Store the current prefix sum if not already present
        preSum.putIfAbsent(sum, i);
    }

    return max;
}
                

Python Implementation:

def maxSubArrayLen(nums, k):
    pre_sum = {0: -1}  # Initialize prefix sum map with 0 at index -1
    total = 0
    max_len = 0

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

        # Check if there exists a subarray sum equals to k
        if total - k in pre_sum:
            max_len = max(max_len, i - pre_sum[total - k])

        # Store the current prefix sum if not already present
        if total not in pre_sum:
            pre_sum[total] = i

    return max_len
                

C++ Implementation:

#include 
#include 
using namespace std;

int maxSubArrayLen(vector& nums, int k) {
    unordered_map preSum;  // Map to store prefix sum and first occurrence
    preSum[0] = -1;  // Initialize with prefix sum of 0 at index -1
    int sum = 0, maxLen = 0;

    for (int i = 0; i < nums.size(); i++) {
        sum += nums[i];

        // Check if there exists a subarray sum equals to k
        if (preSum.find(sum - k) != preSum.end()) {
            maxLen = max(maxLen, i - preSum[sum - k]);
        }

        // Store the current prefix sum if not already present
        if (preSum.find(sum) == preSum.end()) {
            preSum[sum] = i;
        }
    }

    return maxLen;
}