Maximum Size Subarray Sum Equals K - Leetcode Solution

Problem Statement:

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

Example:

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.

Solution:

Approach:

To solve this problem we will use a HashMap to store the prefix sum and their corresponding indices. The prefix sum will be calculated by adding the previous sum of i-th element with the current element at index i. If the sum of elements between two indices i and j is equal to k, then the sum of elements between the indices i+1 and j will also be equal to k. We can take advantage of this property by storing the prefix sums we have seen so far in a HashMap along with their corresponding indices. While iterating over the array, we can check if the sum of the subarray from the start of the array, i.e., the prefix sum, up to the current index equals k. If it does, we update the length of the max subarray, which ends at the current index.

Step by Step Solution:

1. Initialize a HashMap called ‘prefix_sum’ and a variable called ‘max_length’ to store the maximum length of the subarray.

2. Initialize a variable called ‘curr_sum’ to store the current sum of the elements.

3. Iterate over the array ‘nums’ and calculate the prefix sum at each index by adding the value at the current index to the sum of the previous elements.

   3.1. If the current sum minus k exists in the ‘prefix_sum’ HashMap, it means that there is a subarray that exists between the current index and the index where the sum was first seen, and the sum of those elements in the subarray is equal to k. We update the value of ‘max_length’ if the length of the subarray is greater than the current value of ‘max_length’.

   3.2. If the prefix sum is equal to k, we update the value of ‘max_length’ to 1 if it is greater than or equal to the current value.

   3.3. If the prefix sum does not exist in the HashMap, we add it with the current index as value.

4. After iterating over the array, return the value of ‘max_length’.

Time Complexity:

The time complexity of this solution is O(n) because we iterate over the array only once.

Space Complexity:

The space complexity of this solution is O(n) because we store the prefix sums in a HashMap.

Code Implementation:

Python:

class Solution: def maxSubArrayLen(self, nums: List[int], k: int) -> int: prefix_sum = {} prefix_sum[0] = -1 max_length = 0 curr_sum = 0 for i in range(len(nums)): curr_sum += nums[i] if curr_sum - k in prefix_sum: max_length = max(max_length, i - prefix_sum[curr_sum - k]) if curr_sum not in prefix_sum: prefix_sum[curr_sum] = i if curr_sum == k: max_length = max(max_length, i + 1) return max_length

Java:

class Solution { public int maxSubArrayLen(int[] nums, int k) { HashMap<Integer, Integer> prefix_sum = new HashMap<>(); prefix_sum.put(0, -1); int max_length = 0; int curr_sum = 0; for (int i = 0; i < nums.length; i++) { curr_sum += nums[i]; if (prefix_sum.containsKey(curr_sum - k)) { max_length = Math.max(max_length, i - prefix_sum.get(curr_sum - k)); } if (!prefix_sum.containsKey(curr_sum)) { prefix_sum.put(curr_sum, i); } if (curr_sum == k) { max_length = Math.max(max_length, i + 1); } } return max_length; } }

1