Binary Subarrays With Sum

Interview Problem Intermediate Medium Prefix Sum Array Hash Map

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.numSubarraysWithSum(nums, goal). nums contains only zero and one. Return the number of non-empty contiguous subarrays whose sum equals goal.

Starter code

class Solution:
    def numSubarraysWithSum(self, nums, goal):
        pass

Test cases

goal-two

{
  "args": [
    [
      1,
      0,
      1,
      0,
      1
    ],
    2
  ]
}

Expected: 4

Wizard outline

Step 1: Initialize Solution.numSubarraysWithSum
Replace the empty starter with the first real state owned by Solution.numSubarraysWithSum. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Whole Prefix case
Complete the readable core algorithm for one representative Interview case. For each current prefix, count earlier prefixes equal to current-goal.
Step 4: Harden the All Zero boundary
Repair the reviewed boundary and pass the complete submission contract. A subarray ending at the current index has sum goal exactly when its preceding prefix equals current-goal. The map counts every such start, so adding that frequency counts each valid subarray once at its unique ending index.

Footguns and prerequisites

Seed prefix frequency zero with one occurrence so subarrays beginning at index zero are counted.
arrays strings two pointers sliding window
hashing and sets

Reviewed references

LeetCode 930 — Binary Subarrays With Sum

Practice prerequisites

Build Prefix Aggregates(opens in a new tab)
Build Prefix Aggregates isolates after consuming i values, the final aggregate equals sum(values[:i]) and the list has i + 1 entries. That focused state discipline is required when implementing binary subarrays with sum as a complete Interview Problem.

Recommended approach and implementation

Maintain the current prefix sum and a frequency map of all earlier prefixes; add frequency[current-goal] before recording current.

Why it works: A subarray ending at the current index has sum goal exactly when its preceding prefix equals current-goal. The map counts every such start, so adding that frequency counts each valid subarray once at its unique ending index.

class Solution:
    def numSubarraysWithSum(self, nums, goal):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        frequencies = {0: 1}
        prefix = 0
        total = 0
        for value in nums:
            prefix += value
            total += frequencies.get(prefix - goal, 0)
            frequencies[prefix] = frequencies.get(prefix, 0) + 1
        return total