Maximum Size Subarray Sum Equals k

Leet Code Link - https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/description/

Complexity - Medium

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 * 105
-104 <= nums[i] <= 104
-109 <= k <= 109

Solution

• Initialize three variables:

• An integer prefixSum that keeps track of the prefix sum of nums as 0.

• An integer longestSubarray that will keep track of the longest subarray with sum k as 0.

• A hash map indices that has keys of prefix sums seen so far and values of the first index that each key was seen.

• Iterate through nums. At each index i, add nums[i] to prefixSum. Then, make the following checks:

• If prefixSum == k, that means the sum of the array up to this index is equal to k. Update longestSubarray = i + 1 (because i is 0-indexed)

• If prefixSum - k exists in indices, that means there is a subarray with sum k ending at the current i. The length will be i - indices[prefixSum - k]. If this length is greater than longestSubarray, update longestSubarray.

• If the current prefixSum does not yet exist in indices, then set indices[prefixSum] = i. Only do this if it does not already exist because we only want the earliest instance of this presum.

• Return longestSubarray.

class Solution {
    
    public int maxSubArrayLen(int[] nums, int k) {
        HashMap<Integer,Integer> prefixSum = new HashMap<>();
                prefixSum.put(0, -1);
        int prefix = 0;int longestSubarray = 0;
        for(int i=0;i<nums.length;i++){
            prefix+=nums[i];

            if(prefixSum.containsKey(prefix-k)){
                longestSubarray = Math.max(longestSubarray,i-prefixSum.get(prefix-k));
            }
            if(!prefixSum.containsKey(prefix)){
                prefixSum.put(prefix,i);
            }
        }
        return longestSubarray;
    }
}

Complexity

Given N as the length of nums,

Time complexity: O(N)

We only make one pass through nums, each time doing a constant amount of work. All hash map operations are O(1).

Space complexity: O(N)

Our hash map can potentially hold as many key-value pairs as there are numbers in nums. An example of this is when there are no negative numbers in the array.