Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Binary Subarrays With Sum (medium)

Problem Statement

Given a binary called nums and an integer called goal, return the number of subarrays that have a sum equal to goal.

A subarray is a part of the array that is continuous, meaning all its elements are next to each other.

Examples

Example 1

  • Input: nums = [1, 1, 0, 1, 1], goal = 2
  • Expected Output: 5
  • Justification: The subarrays with a sum of 2 are: [1, 1] (from index 0 to 1), [1, 1, 0] (from index 0 to 2), [1, 0, 1] (from index 1 to 3), [0, 1, 1] (from index 2 to 5), and [1, 1] (from index 4 to 5).

.....

.....

.....

Like the course? Get enrolled and start learning!
S

Sandip Bhattacharya

· 2 years ago

In Example 1: Wrong: "Justification: The subarrays with a sum of 3"

Right: "Justification: The subarrays with a sum of 2"

Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:

    def numSubarraysWithSum(self, nums, goal):
        count = 0
        j = 0

        add = 0

        for i in range(len(nums)):
            
            add += nums[i]

            # move j only if add becomes larger than goal 0
            while add > goal:
                add -= nums[j]
                j += 1

            if add == goal:
                count += 1 # without prefix 0

                # j wont move but we want to count all the prefix 0 . 
                # like 0 0 1 1 goal 2 answer = 3
                k = j 
                while nums[k] == 0:
                    count += 1
                    k += 1

        return count