Maximum Size Subarray Sum Equals k Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple Facebook Goldman Sachs Microsoft Palantir Technologies
Array Hash MapViews 4013

Problem Statement:

The Maximum Size Subarray Sum Equals k Leetcode Solution – Given an integer array nums and integer k, return the maximum length of a subarray that sums to k. If there is not one, return 0 instead.

Example:

Input: 
nums = [1,-1,5,-2,3], k = 3
Output: 4

Explanation:

Maximum Size Subarray Sum Equals k Leetcode Solution

 

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.

Approach:

Idea:

We are using prefix sum and hash map to solve this problem.

  1. Initialize three variables: “curr”, “len”, and a hash map “mpp”. “curr” variable is used to store the prefix sum, “len” that will keep track of the longest subarray with sum k as 0 and a hash map “mpp” that has keys of prefix sums seen so far and values of the first index that each key was seen.
  2. Iterate through the given array and calculate the curr variable but add the current value of the array element.
  3. Now in the loop, we check that if the curr variable is equal to the given target k, means the sum of the array up to this index is equal to k. Update len = i+1.
  4. If curr-k exists in mpp, that means there is a subarray with sum k ending at the current i. The length will be  i-mpp[curr-k]. If this length is greater than len, update len.
  5. If the current curr does not yet exist in mpp, then set mpp[curr]=i.
  6. Return maximum value of len.

 

Code:

C++ Program of  Maximum Size Subarray Sum Equals k Leetcode Solution:

class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        long long curr=0;
        int len=0;
        unordered_map<long long, int> mpp;
        for(int i=0;i<nums.size();i++){
            curr+=nums[i];
            if(curr==k){
                len=i+1;
            }
            else if(mpp.find(curr-k)!=mpp.end()){
                len=max(len, i-mpp[curr-k]);
            }
            if(mpp.find(curr)==mpp.end()){
                mpp[curr]=i;
            }
        }
        return len;
    }
};

Java Program of  Maximum Size Subarray Sum Equals k Leetcode Solution:

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

Complexity Analysis:

Time Complexity:

Time Complexity will be O(N) as we iterate over the given array nums (of length N) once, where N is the size of the input array.

Space Complexity:

Space Complexity will be O(N) as we need another hash map to solve this problem, where N is the size of the input array.

Translate »