930. Binary Subarrays with Sum - Explanation

Description

You are given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum goal.

A subarray is a contiguous part of the array.

Example 1:

Input: nums = [1,0,1,0,1], goal = 2

Output: 4

Explanation: The 4 subarrays are bolded and underlined below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]

Example 2:

Input: nums = [0,0,0,0,0], goal = 0

Output: 15

Constraints:

1 <= nums.length <= 30,000
nums[i] is either 0 or 1.
0 <= goal <= nums.length

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        n, res = len(nums), 0

        for i in range(n):
            curSum = 0
            for j in range(i, n):
                curSum += nums[j]
                if curSum == goal:
                    res += 1

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Prefix Sum + Hash Map

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        prefixSum = 0
        count = { 0 : 1 } # prefixSum -> count
        res = 0

        for num in nums:
            prefixSum += num
            res += count.get(prefixSum - goal, 0)
            count[prefixSum] = count.get(prefixSum, 0) + 1

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Prefix Sum + Array

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        n = len(nums)
        count = [0] * (n + 1)
        count[0] = 1
        prefixSum, res = 0, 0

        for num in nums:
            prefixSum += num
            if prefixSum >= goal:
                res += count[prefixSum - goal]
            count[prefixSum] += 1

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Sliding Window

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        def helper(x):
            if x < 0:
                return 0
            res = l = cur = 0
            for r in range(len(nums)):
                cur += nums[r]
                while cur > x:
                    cur -= nums[l]
                    l += 1
                res += (r - l + 1)
            return res

        return helper(goal) - helper(goal - 1)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$