Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/930.html

930. Binary Subarrays With Sum

Level

Medium

Description

In an array A of 0s and 1s, how many non-empty subarrays have sum S?

Example 1:

Input: A = [1,0,1,0,1], S = 2

Output: 4

Explanation:

The 4 subarrays are bolded below:

[1,0,1,0,1]

[1,0,1,0,1]

[1,0,1,0,1]

[1,0,1,0,1]

Note:

  1. A.length <= 30000
  2. 0 <= S <= A.length
  3. A[i] is either 0 or 1.

Solution

Use a map to count the number of subarrays starting from index 0 that have sum equal to a given value.

If S is 0, then for each possible sum in the map, count the number of subarrays of the sum. If there are k such subarrays, then the number of non-empty subarrays obtained from such subarrays is k * (k - 1) / 2. Count the number of non-empty subarrays with sum 0 from all possible sums in the map.

If S is positive, then for each pair (i, i + S) such that i >= 0 and i + S doesn’t exceed the maximum possible sum (which is the sum of all numbers in the array), let count1 and count2 be the numbers of subarrays starting from index 0 that have sum i and sum i + S respectively, and the number of non-empty subarrays with sum S for the pair (i, i + S) is count1 * count2. Count the number of non-empty subarrays with sum S from all possible sums in the map.

  • class Solution {
        public int numSubarraysWithSum(int[] A, int S) {
            if (A == null || A.length == 0)
                return 0;
            Map<Integer, Integer> sumCountMap = new HashMap<Integer, Integer>();
            int length = A.length;
            int beginIndex = 0;
            int curSum = A[0];
            for (int i = 1; i < length; i++) {
                if (A[i] == 1) {
                    sumCountMap.put(curSum, i - beginIndex);
                    curSum++;
                    beginIndex = i;
                }
            }
            sumCountMap.put(curSum, length - beginIndex);
            int totalCount = 0;
            sumCountMap.put(0, sumCountMap.getOrDefault(0, 0) + 1);
            if (S == 0) {
                Set<Integer> keySet = sumCountMap.keySet();
                for (int num : keySet) {
                    int count = sumCountMap.get(num);
                    totalCount += count * (count - 1) / 2;
                }
                return totalCount;
            } else {
                int minSum = A[0], maxSum = curSum;
                int upper = maxSum - S;
                for (int i = 0; i <= upper; i++) {
                    int count1 = sumCountMap.get(i), count2 = sumCountMap.get(i + S);
                    totalCount += count1 * count2;
                }
                return totalCount;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/binary-subarrays-with-sum/
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
        int numSubarraysWithSum(vector<int>& A, int goal) {
            unordered_map<int, int> m{ {0,-1} }; // count of 1s -> index
            int ans = 0;
            for (int i = 0, N = A.size(), sum = 0; i < N; ++i) {
                sum += A[i];
                if (m.count(sum) == 0) m[sum] = i;
                if (goal == 0) ans += i - m[sum];
                else if (sum - goal >= 0) ans += m[sum - goal + 1] - m[sum - goal];
            }
            return ans;
        }
    };
    
  • class Solution:
        def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
            i1 = i2 = s1 = s2 = j = ans = 0
            n = len(nums)
            while j < n:
                s1 += nums[j]
                s2 += nums[j]
                while i1 <= j and s1 > goal:
                    s1 -= nums[i1]
                    i1 += 1
                while i2 <= j and s2 >= goal:
                    s2 -= nums[i2]
                    i2 += 1
                ans += i2 - i1
                j += 1
            return ans
    
    ############
    
    class Solution(object):
        def numSubarraysWithSum(self, A, S):
            """
            :type A: List[int]
            :type S: int
            :rtype: int
            """
            N = len(A)
            tsum = [0] * (N + 1)
            for i in range(1, N + 1):
                tsum[i] = tsum[i - 1] + A[i - 1]
            res = 0
            for i in range(1, N + 1):
                remain = tsum[i] - S
                if remain < 0:
                    continue
                left = bisect.bisect_left(tsum, remain)
                right = bisect.bisect_right(tsum, remain)
                right = min(i, right)
                res += right - left
            return res
    
  • func numSubarraysWithSum(nums []int, goal int) int {
    	i1, i2, s1, s2, j, ans, n := 0, 0, 0, 0, 0, 0, len(nums)
    	for j < n {
    		s1 += nums[j]
    		s2 += nums[j]
    		for i1 <= j && s1 > goal {
    			s1 -= nums[i1]
    			i1++
    		}
    		for i2 <= j && s2 >= goal {
    			s2 -= nums[i2]
    			i2++
    		}
    		ans += i2 - i1
    		j++
    	}
    	return ans
    }
    
  • /**
     * @param {number[]} nums
     * @param {number} goal
     * @return {number}
     */
    var numSubarraysWithSum = function (nums, goal) {
        let i1 = 0,
            i2 = 0,
            s1 = 0,
            s2 = 0,
            j = 0,
            ans = 0;
        const n = nums.length;
        while (j < n) {
            s1 += nums[j];
            s2 += nums[j];
            while (i1 <= j && s1 > goal) s1 -= nums[i1++];
            while (i2 <= j && s2 >= goal) s2 -= nums[i2++];
            ans += i2 - i1;
            ++j;
        }
        return ans;
    };
    
    

All Problems

All Solutions