Binary Subarrays With Sum

🎯

Binary Subarrays With Sum

mediumSLIDING_WINDOWAmazonGoogle

Imagine you are analyzing a binary signal stream and want to count how many continuous segments have exactly a certain number of 'on' signals.

💡 This problem asks to count subarrays with a fixed sum in a binary array. Beginners often struggle because the naive approach is too slow and the optimal solution requires understanding prefix sums and sliding windows, which can be unintuitive at first.

📋

Problem Statement

Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum equal to goal. A subarray is a contiguous part of the array.

1 ≤ nums.length ≤ 10^5nums[i] is either 0 or 10 ≤ goal ≤ nums.length

💡

Example

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

Output4

The subarrays with sum 2 are: [1,0,1], [0,1,0,1], [1,0,1], and [1,0,1,0,1] (considering all valid contiguous segments).

• All zeros with goal 0 → count all subarrays of zeros
• All ones with goal equal to length → only one subarray (whole array)
• goal is 0 with mixed zeros and ones → count subarrays with no ones
• Single element array with goal 0 or 1 → either 1 or 0 subarrays

⚠️

Common Mistakes

Recomputing sum from scratch inside nested loops

Leads to O(n^3) time and TLE

✅ Accumulate sum incrementally in inner loop

Not initializing prefix sum count map with {0:1}

Misses counting subarrays starting at index 0

✅ Always initialize prefix_counts with 0 mapped to 1

Using sliding window approach on arrays with negative numbers

Incorrect results or infinite loops

✅ Use prefix sums with hashmap for arrays with negatives

Off-by-one errors in sliding window boundaries

Incorrect counts or runtime errors

✅ Carefully update left pointer and count subarrays as right - left + 1

Not handling goal = 0 case separately in sliding window

Incorrect result when goal is zero

✅ Return atMost(0) directly when goal is zero

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem deeply by explicitly enumerating all subarrays and checking their sums, even though it's inefficient.

Intuition

Try every possible subarray and sum its elements to check if it equals the goal.

Algorithm

1. Initialize count to 0.
2. Use two nested loops: outer loop picks start index, inner loop picks end index.
3. Sum elements from start to end index.
4. If sum equals goal, increment count.

💡 The nested loops make it easy to understand but hard to scale; beginners often miss the need to sum incrementally to avoid recomputing sums.

</>

Code

def numSubarraysWithSum(nums, goal):
    count = 0
    n = len(nums)
    for start in range(n):
        current_sum = 0
        for end in range(start, n):
            current_sum += nums[end]
            if current_sum == goal:
                count += 1
    return count

# Driver code
if __name__ == '__main__':
    print(numSubarraysWithSum([1,0,1,0,1], 2))  # Output: 4

Line Notes

count = 0Initialize count to track number of valid subarrays

for start in range(n)Outer loop selects the start index of subarray

current_sum += nums[end]Incrementally add current element to avoid recomputing sum from scratch

if current_sum == goalCheck if current subarray sum matches the goal

public class Solution {
    public static int numSubarraysWithSum(int[] nums, int goal) {
        int count = 0;
        int n = nums.length;
        for (int start = 0; start < n; start++) {
            int currentSum = 0;
            for (int end = start; end < n; end++) {
                currentSum += nums[end];
                if (currentSum == goal) {
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(numSubarraysWithSum(new int[]{1,0,1,0,1}, 2)); // Output: 4
    }
}

Line Notes

int count = 0;Initialize count to accumulate valid subarrays

for (int start = 0; start < n; start++)Outer loop picks start index

currentSum += nums[end];Add current element to running sum

if (currentSum == goal)Check if subarray sum equals goal

#include <iostream>
#include <vector>
using namespace std;

int numSubarraysWithSum(vector<int>& nums, int goal) {
    int count = 0;
    int n = nums.size();
    for (int start = 0; start < n; start++) {
        int currentSum = 0;
        for (int end = start; end < n; end++) {
            currentSum += nums[end];
            if (currentSum == goal) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    vector<int> nums = {1,0,1,0,1};
    cout << numSubarraysWithSum(nums, 2) << endl; // Output: 4
    return 0;
}

Line Notes

int count = 0;Initialize count for valid subarrays

for (int start = 0; start < n; start++)Outer loop selects start index

currentSum += nums[end];Add current element to current sum

if (currentSum == goal)Check if current sum matches goal

function numSubarraysWithSum(nums, goal) {
    let count = 0;
    const n = nums.length;
    for (let start = 0; start < n; start++) {
        let currentSum = 0;
        for (let end = start; end < n; end++) {
            currentSum += nums[end];
            if (currentSum === goal) {
                count++;
            }
        }
    }
    return count;
}

// Test
console.log(numSubarraysWithSum([1,0,1,0,1], 2)); // Output: 4

Line Notes

let count = 0;Initialize count to track valid subarrays

for (let start = 0; start < n; start++)Outer loop picks start index

currentSum += nums[end];Add current element to running sum

if (currentSum === goal)Check if subarray sum equals goal

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each can run up to n times, summing subarrays incrementally to avoid recomputing sums from scratch.

💡 For n=20, this means about 400 operations, which is okay, but for n=100000, it becomes 10 billion operations, which is too slow.

Interview Verdict: TLE

This approach is too slow for large inputs, but it is a good starting point to understand the problem before optimizing.

🧠

Prefix Sum + Hash Map Counting

💡 This approach uses prefix sums and a hash map to count how many prefix sums have appeared, enabling O(n) counting of subarrays with sum equal to goal.

Intuition

Use prefix sums to represent sums of subarrays and count how many prefix sums differ by goal to find valid subarrays efficiently.

Algorithm

1. Initialize a hash map to count prefix sums and set count of sum 0 to 1.
2. Iterate through the array, computing the running prefix sum.
3. For each prefix sum, check if prefix_sum - goal exists in the map; if yes, add its count to result.
4. Update the map with the current prefix sum count.

💡 The key insight is that subarray sums can be found by differences of prefix sums, and counting these differences efficiently avoids nested loops.

</>

Code

def numSubarraysWithSum(nums, goal):
    prefix_counts = {0: 1}
    prefix_sum = 0
    count = 0
    for num in nums:
        prefix_sum += num
        if prefix_sum - goal in prefix_counts:
            count += prefix_counts[prefix_sum - goal]
        prefix_counts[prefix_sum] = prefix_counts.get(prefix_sum, 0) + 1
    return count

# Driver code
if __name__ == '__main__':
    print(numSubarraysWithSum([1,0,1,0,1], 2))  # Output: 4

Line Notes

prefix_counts = {0: 1}Initialize map with sum 0 count 1 to handle subarrays starting at index 0

prefix_sum += numUpdate running prefix sum with current element

if prefix_sum - goal in prefix_countsCheck if a prefix sum exists that forms a subarray summing to goal

prefix_counts[prefix_sum] = prefix_counts.get(prefix_sum, 0) + 1Increment count of current prefix sum in map

import java.util.HashMap;

public class Solution {
    public static int numSubarraysWithSum(int[] nums, int goal) {
        HashMap<Integer, Integer> prefixCounts = new HashMap<>();
        prefixCounts.put(0, 1);
        int prefixSum = 0, count = 0;
        for (int num : nums) {
            prefixSum += num;
            count += prefixCounts.getOrDefault(prefixSum - goal, 0);
            prefixCounts.put(prefixSum, prefixCounts.getOrDefault(prefixSum, 0) + 1);
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(numSubarraysWithSum(new int[]{1,0,1,0,1}, 2)); // Output: 4
    }
}

Line Notes

prefixCounts.put(0, 1);Initialize map with sum 0 count 1 for subarrays starting at index 0

prefixSum += num;Add current element to running prefix sum

count += prefixCounts.getOrDefault(prefixSum - goal, 0);Add count of prefix sums that form subarray with sum goal

prefixCounts.put(prefixSum, prefixCounts.getOrDefault(prefixSum, 0) + 1);Update count of current prefix sum

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int numSubarraysWithSum(vector<int>& nums, int goal) {
    unordered_map<int, int> prefixCounts;
    prefixCounts[0] = 1;
    int prefixSum = 0, count = 0;
    for (int num : nums) {
        prefixSum += num;
        if (prefixCounts.find(prefixSum - goal) != prefixCounts.end()) {
            count += prefixCounts[prefixSum - goal];
        }
        prefixCounts[prefixSum]++;
    }
    return count;
}

int main() {
    vector<int> nums = {1,0,1,0,1};
    cout << numSubarraysWithSum(nums, 2) << endl; // Output: 4
    return 0;
}

Line Notes

prefixCounts[0] = 1;Initialize map with sum 0 count 1 for subarrays starting at index 0

prefixSum += num;Add current element to running prefix sum

if (prefixCounts.find(prefixSum - goal) != prefixCounts.end())Check if prefix sum difference exists to form goal

prefixCounts[prefixSum]++;Increment count of current prefix sum

function numSubarraysWithSum(nums, goal) {
    const prefixCounts = new Map();
    prefixCounts.set(0, 1);
    let prefixSum = 0, count = 0;
    for (const num of nums) {
        prefixSum += num;
        count += prefixCounts.get(prefixSum - goal) || 0;
        prefixCounts.set(prefixSum, (prefixCounts.get(prefixSum) || 0) + 1);
    }
    return count;
}

// Test
console.log(numSubarraysWithSum([1,0,1,0,1], 2)); // Output: 4

Line Notes

prefixCounts.set(0, 1);Initialize map with sum 0 count 1 for subarrays starting at index 0

prefixSum += num;Add current element to running prefix sum

count += prefixCounts.get(prefixSum - goal) || 0;Add count of prefix sums that form subarray with sum goal

prefixCounts.set(prefixSum, (prefixCounts.get(prefixSum) || 0) + 1);Update count of current prefix sum

⏱

Complexity

TimeO(n)

SpaceO(n)

Single pass through the array with constant time hash map operations; space for prefix sums map.

💡 For n=100000, this means about 100000 operations, which is efficient and scalable.

Interview Verdict: Accepted

This approach is efficient and passes all tests, making it a practical solution for interviews.

🧠

Two Pointers / Sliding Window for Binary Arrays

💡 This approach uses two sliding windows to count subarrays with sum exactly equal to goal by counting subarrays with sum at most goal and at most goal-1.

Intuition

Count subarrays with sum ≤ goal and subtract those with sum ≤ goal-1 to get count of subarrays with sum exactly goal.

Algorithm

1. Define a helper function to count subarrays with sum at most S using two pointers.
2. Use this helper to count subarrays with sum ≤ goal and sum ≤ goal-1.
3. Return the difference of these two counts as the final answer.

💡 The key insight is that counting subarrays with sum exactly goal is equivalent to difference of counts of subarrays with sum at most goal and at most goal-1.

</>

Code

def numSubarraysWithSum(nums, goal):
    def atMost(S):
        count = left = 0
        current_sum = 0
        for right, num in enumerate(nums):
            current_sum += num
            while current_sum > S:
                current_sum -= nums[left]
                left += 1
            count += right - left + 1
        return count
    return atMost(goal) - atMost(goal - 1) if goal > 0 else atMost(0)

# Driver code
if __name__ == '__main__':
    print(numSubarraysWithSum([1,0,1,0,1], 2))  # Output: 4

Line Notes

def atMost(S):Helper counts subarrays with sum at most S

while current_sum > S:Shrink window from left until sum ≤ S

count += right - left + 1Add number of valid subarrays ending at right

return atMost(goal) - atMost(goal - 1)Difference gives count of subarrays with sum exactly goal

public class Solution {
    private static int atMost(int[] nums, int S) {
        int count = 0, left = 0, currentSum = 0;
        for (int right = 0; right < nums.length; right++) {
            currentSum += nums[right];
            while (currentSum > S) {
                currentSum -= nums[left++];
            }
            count += right - left + 1;
        }
        return count;
    }

    public static int numSubarraysWithSum(int[] nums, int goal) {
        if (goal == 0) return atMost(nums, 0);
        return atMost(nums, goal) - atMost(nums, goal - 1);
    }

    public static void main(String[] args) {
        System.out.println(numSubarraysWithSum(new int[]{1,0,1,0,1}, 2)); // Output: 4
    }
}

Line Notes

private static int atMost(int[] nums, int S)Helper counts subarrays with sum at most S

while (currentSum > S)Shrink window from left to maintain sum ≤ S

count += right - left + 1;Add count of valid subarrays ending at right

return atMost(nums, goal) - atMost(nums, goal - 1);Difference yields exact count of subarrays with sum goal

#include <iostream>
#include <vector>
using namespace std;

int atMost(const vector<int>& nums, int S) {
    int count = 0, left = 0, currentSum = 0;
    for (int right = 0; right < (int)nums.size(); right++) {
        currentSum += nums[right];
        while (currentSum > S) {
            currentSum -= nums[left++];
        }
        count += right - left + 1;
    }
    return count;
}

int numSubarraysWithSum(vector<int>& nums, int goal) {
    if (goal == 0) return atMost(nums, 0);
    return atMost(nums, goal) - atMost(nums, goal - 1);
}

int main() {
    vector<int> nums = {1,0,1,0,1};
    cout << numSubarraysWithSum(nums, 2) << endl; // Output: 4
    return 0;
}

Line Notes

int atMost(const vector<int>& nums, int S)Helper function counts subarrays with sum ≤ S

while (currentSum > S)Shrink window from left to keep sum ≤ S

count += right - left + 1;Add count of valid subarrays ending at right

return atMost(nums, goal) - atMost(nums, goal - 1);Difference gives count of subarrays with sum exactly goal

function numSubarraysWithSum(nums, goal) {
    function atMost(S) {
        let count = 0, left = 0, currentSum = 0;
        for (let right = 0; right < nums.length; right++) {
            currentSum += nums[right];
            while (currentSum > S) {
                currentSum -= nums[left++];
            }
            count += right - left + 1;
        }
        return count;
    }
    if (goal === 0) return atMost(0);
    return atMost(goal) - atMost(goal - 1);
}

// Test
console.log(numSubarraysWithSum([1,0,1,0,1], 2)); // Output: 4

Line Notes

function atMost(S)Helper counts subarrays with sum at most S

while (currentSum > S)Shrink window from left to maintain sum ≤ S

count += right - left + 1;Add count of valid subarrays ending at right

return atMost(goal) - atMost(goal - 1);Difference yields exact count of subarrays with sum goal

⏱

Complexity

TimeO(n)

SpaceO(1)

Each element is visited at most twice by the two pointers, and only constant extra space is used.

💡 For n=100000, this means about 200000 operations, very efficient and uses minimal memory.

Interview Verdict: Accepted

This approach is optimal in time and space for this problem and is a great demonstration of sliding window technique.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, coding the prefix sum + hashmap or sliding window approach is best; brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code
2. Prefix Sum + Hash Map	O(n)	O(n)	No	N/A	Code this for general arrays
3. Two Pointers / Sliding Window	O(n)	O(1)	No	N/A	Code this for binary arrays for optimal space

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force approach to show understanding.Step 3: Discuss prefix sums and hash map optimization.Step 4: Present the sliding window approach as the optimal solution.Step 5: Code the chosen approach carefully and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize from brute force, knowledge of prefix sums and sliding windows, and coding accuracy.

Common Follow-ups

• What if the array contains negative numbers? → Sliding window won't work; prefix sums with hashmap still applies.
• Can you find the longest subarray with sum equal to goal? → Use prefix sums and hashmap to track earliest indices.

💡 These follow-ups test your understanding of the limitations of sliding window and your ability to adapt prefix sums for variations.

🔍

Pattern Recognition

When to Use

1) Problem involves counting subarrays with a fixed sum; 2) Array contains only 0s and 1s; 3) Need efficient O(n) solution; 4) Sliding window or prefix sums are hinted.

Signature Phrases

'number of subarrays with sum equal to goal''binary array''count subarrays'

NOT This Pattern When

Problems asking for maximum/minimum length subarray without sum constraints or with negative numbers only

Similar Problems

Subarray Sum Equals K - generalizes to any integersMinimum Size Subarray Sum - uses variable size sliding windowNumber of Subarrays with Bounded Maximum - counts subarrays with constraints

Practice

1. You are given a string and need to find the length of the longest substring where no character repeats. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Brute force checking all substrings and verifying uniqueness by sorting each substring

B. Sliding window with a hash map tracking the last seen index of each character to dynamically adjust the window

C. Dynamic programming by storing longest substring lengths ending at each index without duplicates

D. Greedy approach by always extending the substring until a duplicate is found, then restarting from next character

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the longest substring without repeating characters, which suggests a variable-size window to track unique characters efficiently.

2. Step 2: Evaluate approaches

   Brute force and greedy approaches either have high time complexity or fail to adjust the window correctly. Dynamic programming is not straightforward here. The sliding window with a hash map efficiently tracks last seen indices and adjusts the window in O(n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window with index tracking is the known optimal pattern [OK]

Hint: Sliding window with index map -> O(n) solution [OK]

Common Mistakes:

• Confusing greedy restart with sliding window
• Using DP without clear state definition

2. What is the time complexity of the sliding window solution for finding the maximum average subarray of size k in an array of length n, and why might some candidates mistakenly think it is higher?

medium

A. O(n) because each element is added and removed exactly once from the window sum

B. O(n*k) because each window sum is recomputed from scratch

C. O(n log k) due to sorting elements within each window

D. O(k) because the window size dominates the computation

Solution

1. Step 1: Analyze loop operations

   The sliding window sums are updated by adding one new element and removing one old element per iteration, so each element is processed twice.

2. Step 2: Identify complexity

   Since the loop runs n-k times and each iteration is O(1), total time is O(n). The common mistake is thinking sum is recomputed fully each time, which is O(n*k).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window updates sum in constant time per iteration [OK]

Hint: Sliding window updates sum in O(1) per iteration [OK]

Common Mistakes:

• Assuming sum recomputed fully each window
• Confusing window size k with input size n

3. The following code attempts to find the maximum average subarray of size k using a sliding window. Identify the line containing the subtle bug that could cause incorrect results or runtime errors.

medium

A. Line 3: initializing current_sum with sum of first k elements

B. Line 6: updating current_sum by adding nums[i] and nums[i - k]

C. Line 5: loop range starting from k to n

D. Line 8: updating max_sum if current_sum is greater

Solution

1. Step 1: Examine update to current_sum

   The line adds nums[i] and nums[i - k], but it should add nums[i] and subtract nums[i - k] to slide the window correctly.

2. Step 2: Identify impact of bug

   Adding both elements inflates current_sum incorrectly, leading to wrong maximum average or runtime errors if indices go out of range.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window requires subtracting the element leaving the window [OK]

Hint: Sliding window sum updates by adding new and subtracting old element [OK]

Common Mistakes:

• Using addition instead of subtraction in window update
• Off-by-one errors in loop boundaries

4. Suppose the problem is modified so you can pick cards from the start or end any number of times, including reusing cards multiple times (infinite picks allowed). Which approach correctly adapts to this variant?

hard

A. Use a dynamic programming approach to find the maximum sum of k picks allowing repeated cards from ends.

B. Use prefix sums only on the first k cards from the start, ignoring the end cards.

C. Use a greedy approach that always picks the card with the highest point value from either end until k picks are made.

D. Use the original sliding window approach on the middle subarray since it still finds the minimal subarray to exclude.

Solution

1. Step 1: Understand the new constraint

   Reusing cards means picks are not limited to unique cards; the problem becomes unbounded with repetition allowed.

2. Step 2: Recognize sliding window limitation

   The sliding window approach assumes each card can be picked once; it fails with infinite reuse.

3. Step 3: Use dynamic programming

   DP can model picking cards with repetition from ends, tracking maximum sums for each number of picks.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP handles repeated picks; sliding window does not [OK]

Hint: Reusing cards breaks sliding window; DP needed [OK]

Common Mistakes:

• Assuming sliding window still works with repeated picks
• Greedy fails to consider future picks
• Ignoring picks from the end

5. Suppose the problem is modified so that cards can be reused multiple times, and you want to find the minimum length of a contiguous subarray containing at least k duplicates of the same card. Which modification to the sliding window approach correctly handles this variant?

hard

A. Use a frequency map to count occurrences and shrink window only when count of duplicates is at least k

B. Keep last seen index map as before but move left pointer only when a card appears more than once

C. Use brute force nested loops checking all subarrays for at least k duplicates

D. Use a priority queue to track cards with highest frequency in current window

Solution

1. Step 1: Understand the new requirement

   We need to find subarrays with at least k duplicates of the same card, so tracking counts is necessary.

2. Step 2: Modify sliding window approach

   Using a frequency map allows counting occurrences of each card in the window. We expand right pointer and shrink left pointer to maintain minimal window with count ≥ k.

3. Step 3: Evaluate other options

   Last seen map (B) only tracks last index, insufficient for counts ≥ k. Brute force (C) is correct but inefficient. Priority queue (D) adds unnecessary overhead.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Frequency map + sliding window is standard for counting duplicates [OK]

Hint: Frequency map tracks counts for k duplicates in sliding window [OK]

Common Mistakes:

• Using last seen map only for multiple duplicates
• Ignoring counts and relying on indices