/ Array

Maximum Size Subarray Sum Equals K Leetcode

Problem Statement

‚Äč

Given an Integer Array, find the maximum size of subarray whose sum equals to K.
For example, Given [1,2,-3,3,-1,2,4] and K=3, the subarray [1,2,-3,3] sum equals to 3.


Solution Explanation

This problem is very similar to rest of the subarray sum problems. The initial intution is to find the sum of all numbers at every index i, if it matches with 'K',
store the index in max, keep updating it if and when there is a new index whose sum equals to K.

It works great, but until you realize that there may be an 'i' greater than zero, and another index 'j' where,

    sum(j) - sum(i) = K

To find a potential value like this, we can store the values in a map and retrieve, every time when the above condition matches.

Here's how the code looks like in Java,

    import java.util.HashMap;
import java.util.Map;

public class MaxSubArraySumEqualsK {

	public static void main(String[] args) {
		int[] nums = {1,2,-3,3,-1,2,4};
		System.out.println(findMaxSubArraySumEqualsk(nums,3));
	}
	
	public static int findMaxSubArraySumEqualsk(int[] nums, int k){
		int sum = 0, max = 0;
		Map<Integer,Integer> map = new HashMap<>();
		for(int i=0;i<nums.length;i++){
			sum +=  nums[i];
			if(sum==k){
				max = Math.max(max, i+1);
			}
            //You can store either sum or sum-k, we can use sum-k because when it's 0, we want to use the index value
			int diff = sum -k; 
			if(!map.containsKey(diff)){
				map.put(diff,i);
			}else{
				max = Math.max(max, i - map.get(diff));
			}
		}

		return max;
	}
}

Time Complexity

We traverse through the whole array once and caclulate sum and max index, so the time complexity is O(n), space complexity is O(n) since we use a map.