Leetcode: Maximum number of non-overlapping subarrays with sum equals target

 

This question is asked at Google and is a pretty standard Leetcode question. It is as follows: 

We are given an array, called nums, and an integer, called target. We are going to return the maximum number of non-empty, non-overlapping subarrays such that the sum of the values in each subarray is equal to the target.  Remember, we want 2 NON OVERLAPPING subarrays. 

Our intuition tells us this is a prefix sum algorithm and we need to get the maximum sum of arrays. We need to use 2 pointers, hashmap, and prefix sum. 

Prefix sum is the sum of all the items on the left of an index of an array. Basically the subarray sum is equal to the right prefix sum minus the left prefix sum. 

In the hashmap, the key is the prefix sum and the value is the index of the array. Then we need a value called compliment which is prefixSum - target. The variable called right is the right bound of the subarray. We see if a subarray overlaps and sees from there if the number is greater than the right value, which is when we overlap inside of the array.  We compare comp to right. If comp > right then we have overlapping. We have to get as many subarrays as possible and get the right bound. 

class Solution:

    def maxNonOverlapping(self, nums: List[int], target: int) -> int:

        m = collections.defaultdict(int)

        m[0] = -1

        res = 0; right = -1; pre_sum = 0

        for i in range(len(nums)):

            pre_sum += nums[i]

            compliment = pre_sum-target

            if compliment in m and m[compliment] >= right:

                res += 1

                right = i

            m[pre_sum] = i      

        return res

We compute the compliment, and if the compliment is inside of the hash map and if the compliment is greater than the right then we would increment the number of nonoverlapping subarrays with sum equalling the target. 

If compliment appears in the hashmap, then we find the subarray where the sum is equal to the target. 

So here's the review: