Binary Subarrays With Sum

📋

Problem

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

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

Edge cases: All zeros with goal 0 → count all subarrays of zerosAll ones with goal equal to length → only one subarray (whole array)goal is 0 with mixed zeros and ones → count subarrays with no ones

</>

IDE

def numSubarraysWithSum(nums: list[int], goal: int) -> int:public int numSubarraysWithSum(int[] nums, int goal)int numSubarraysWithSum(vector<int>& nums, int goal)function numSubarraysWithSum(nums, goal)

def numSubarraysWithSum(nums, goal):
    # Write your solution here
    pass

class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int numSubarraysWithSum(vector<int>& nums, int goal) {
    // Write your solution here
    return 0;
}

function numSubarraysWithSum(nums, goal) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Fails to count any subarrays when goal is zero or non-zero due to missing prefix sum logic.✅ Implement prefix sum counting with hashmap to track frequencies of sums.

Wrong: 1Greedy approach counts only first valid subarray instead of all.✅ Count all prefix sum pairs with difference equal to goal, not just first occurrence.

Wrong: n*(n+1)/2 - 1Off-by-one error in counting zero-sum subarrays when goal=0.✅ Use correct formula and careful indexing for zero-sum subarrays.

Wrong: TLEUsing brute force O(n^2) approach on large inputs.✅ Switch to O(n) prefix sum + hashmap counting approach.

✓

Test Cases

Try testing your solution on empty and single-element arrays to catch base cases.

Consider tricky cases where greedy or off-by-one errors might cause wrong counts.

Focus on optimizing your solution to linear time using prefix sums and hashmaps.

t1_01basic

Input{"nums":[1,0,1,0,1],"goal":2}

Expected4

⏱ Performance - must finish in 2000ms

The subarrays with sum 2 are: [1,0,1] at indices (0,2), [0,1,0,1] at indices (1,4), [1,0,1] at indices (2,4), and [1,0,1,0,1] at indices (0,4).

💡 Consider prefix sums and how to count subarrays with a given sum.

💡 Use a hashmap to store counts of prefix sums encountered so far.

💡 For each prefix sum, add counts of prefix sums that differ by goal.

Why it failed: Incorrect count likely due to missing some subarrays or miscounting prefix sums. Fix by correctly tracking prefix sums and their frequencies.

✓ Correctly counts all subarrays with sum equal to goal.

t1_02basic

Input{"nums":[0,0,1,0,1],"goal":1}

Expected8

⏱ Performance - must finish in 2000ms

Subarrays with sum 1 are: [0,0,1], [0,1], [1], [1,0], [0,1], and [1].

💡 Remember zeros can be part of subarrays that sum to goal.

💡 Count prefix sums and their frequencies to find valid subarrays.

💡 Check for prefix sums that differ by goal to count subarrays.

Why it failed: Missing subarrays containing zeros or miscounting prefix sums. Fix by including zeros in prefix sums and counting all valid pairs.

✓ Handles zeros correctly and counts all valid subarrays.

t2_01edge

Input{"nums":[],"goal":0}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has no subarrays, so count is 0.

💡 Check behavior when input array is empty.

💡 No subarrays exist if array length is zero.

💡 Return 0 immediately for empty input.

Why it failed: Code crashes or returns non-zero for empty input. Fix by handling empty array case explicitly.

✓ Correctly returns 0 for empty input.

t2_02edge

Input{"nums":[1],"goal":1}

Expected1

⏱ Performance - must finish in 2000ms

Single element array with value 1 and goal 1 has exactly one subarray: the element itself.

💡 Test single element arrays for correctness.

💡 Subarray can be the entire array if sum matches goal.

💡 Return 1 if single element equals goal, else 0.

Why it failed: Fails single element test by returning 0 or wrong count. Fix by checking single element equals goal.

✓ Correctly counts single element subarray matching goal.

t2_03edge

Input{"nums":[0,0,0,0],"goal":0}

Expected10

⏱ Performance - must finish in 2000ms

All zeros with goal 0: count all subarrays of zeros. Number of subarrays = n*(n+1)/2 = 4*5/2=10.

💡 When goal is zero, count subarrays with sum zero (all zeros).

💡 Count all contiguous zero segments and their sub-subarrays.

💡 Use formula n*(n+1)/2 for continuous zeros.

Why it failed: Fails to count zero-sum subarrays correctly when goal=0. Fix by counting all zero-only subarrays.

✓ Correctly counts all zero-sum subarrays for goal=0.

t3_01corner

Input{"nums":[1,1,1,1],"goal":2}

Expected3

⏱ Performance - must finish in 2000ms

Subarrays with sum 2 are: [1,1] at indices (0,1), (1,2), and (2,3).

💡 Check if your solution handles overlapping subarrays correctly.

💡 Avoid greedy approaches that pick only first valid subarray.

💡 Use prefix sums and count all valid pairs, not just first.

Why it failed: Greedy approach counts fewer subarrays by stopping early. Fix by counting all prefix sum pairs with difference goal.

✓ Counts all overlapping subarrays correctly.

t3_02corner

Input{"nums":[0,1,0,1,0],"goal":1}

Expected8

⏱ Performance - must finish in 2000ms

Subarrays with sum 1 include single 1s and zeros around them, total 8.

💡 Beware of confusing 0/1 knapsack style with counting subarrays.

💡 Do not treat problem as unbounded or multiple counts per element.

💡 Use prefix sums and hashmap counting for exact subarray counts.

Why it failed: Confusing 0/1 knapsack or unbounded counting leads to wrong counts. Fix by using prefix sums and counting pairs with difference goal.

✓ Correctly counts subarrays respecting 0/1 constraints.

t3_03corner

Input{"nums":[1,0,0,1,0,1],"goal":2}

Expected5

⏱ Performance - must finish in 2000ms

Subarrays with sum 2 are: [1,0,0,1] (indices 0-3), [1,0,0,1,0] (0-4), [0,0,1,0,1] (1-5), [0,1,0,1] (2-5), [1,0,1] (3-5), [0,1,0,1] (2-5) counted once, and [1,0,1] (3-5) counted once. Total unique subarrays: 7.

💡 Check for off-by-one errors in prefix sum indexing.

💡 Ensure counting all valid subarrays including those with zeros inside.

💡 Use prefix sums and hashmap to count all pairs with difference goal.

Why it failed: Off-by-one errors cause missing subarrays or double counting. Fix by careful prefix sum indexing and counting.

✓ Handles indexing correctly and counts all valid subarrays.

t4_01performance

Input{"nums":[0,1,0,1,1,0,1,0,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0],"goal":50}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 and goal=50 to test O(n) solution efficiency within 2 seconds.

💡 Brute force O(n^2) will time out on large inputs.

💡 Use prefix sums with hashmap for O(n) time complexity.

💡 Avoid nested loops; count prefix sums frequencies instead.

Why it failed: TLE due to O(n^2) brute force approach. Fix by implementing O(n) prefix sum + hashmap counting.

✓ Efficient O(n) solution passes within time limit.

Practice

1. You are given an integer array and a fixed window size k. The task is to find the contiguous subarray of length k that has the maximum average value. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Sliding window technique maintaining a running sum of the current window

B. Brute force nested loops checking all subarrays of size k

C. Dynamic programming with memoization of subproblems

D. Greedy approach selecting the largest elements regardless of position

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the maximum average of any contiguous subarray of fixed size k, which suggests examining all windows of size k.

2. Step 2: Identify optimal approach

   Sliding window maintains a running sum by adding the new element and removing the oldest, achieving O(n) time. Brute force is O(n*k), DP and greedy do not fit this fixed-size window problem optimally.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window updates sum in O(1) per step, total O(n) time [OK]

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

Common Mistakes:

• Thinking greedy works without considering window contiguity
• Assuming DP is needed for fixed-size windows

2. The following code attempts to find the length of the longest substring without repeating characters. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium

A. Line 7: left = index_map[char] + 1

B. Line 6: if char in index_map:

C. Line 5: for right, char in enumerate(s):

D. Line 9: max_len = max(max_len, right - left + 1)

Solution

1. Step 1: Identify the bug in updating left pointer

   The code updates left pointer unconditionally to index_map[char] + 1 when a duplicate is found, but does not check if this moves left backward, which can shrink the window incorrectly.

2. Step 2: Correct approach

   Update left only if index_map[char] + 1 is greater than current left to avoid moving left backward.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing boundary check on left pointer update causes wrong window size [OK]

Hint: Check if left pointer moves backward [OK]

Common Mistakes:

• Not verifying left pointer position before update
• Assuming duplicates always appear after left

3. The following code attempts to find the minimum size subarray sum using a sliding window. Identify the bug that causes incorrect results or infinite loops.

def min_subarray_len(target, nums):
    n = len(nums)
    left = 0
    current_sum = 0
    min_length = float('inf')
    for right in range(n):
        current_sum += nums[right]
        while current_sum > target:
            min_length = min(min_length, right - left + 1)
            current_sum -= nums[left]
            left += 1
    return 0 if min_length == float('inf') else min_length

medium

A. Line with 'while current_sum > target:' should be 'while current_sum >= target:'

B. Line with 'current_sum += nums[right]' should be outside the for loop

C. Line with 'min_length = min(min_length, right - left + 1)' should be after the while loop

D. Line with 'return 0 if min_length == float('inf') else min_length' should return min_length directly

Solution

1. Step 1: Analyze while loop condition

   The condition 'current_sum > target' misses cases where current_sum == target, so minimal subarrays with sum exactly equal to target are ignored.

2. Step 2: Correct condition to include equality

   Changing to 'current_sum >= target' ensures all valid subarrays are considered and window shrinks properly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Equality in condition is critical to find minimal subarray length [OK]

Hint: Use >= to include exact target sums when shrinking window [OK]

Common Mistakes:

• Using > instead of >= in while condition
• Not shrinking window enough
• Returning min_length without checking infinity

4. Suppose you want to find the longest substring with at most k distinct characters, but now characters can be reused infinitely many times and the string is extremely long. Which modification to the sliding window approach is necessary to handle this efficiently?

hard

A. Use a frequency map with counts and shrink window when counts exceed k distinct characters, ignoring last seen positions

B. Maintain an ordered dictionary of last seen indices and shrink window as usual; no change needed

C. Use a frequency map and shrink the window only when distinct characters exceed k, ignoring last seen indices

D. Switch to a brute force approach since reuse breaks sliding window assumptions

Solution

1. Step 1: Understand reuse impact

   When characters can be reused infinitely, tracking last seen indices is insufficient; frequency counts are needed.

2. Step 2: Modify approach

   Use a frequency map to count occurrences and shrink window when distinct characters exceed k, ignoring last seen positions.

3. Step 3: Confirm efficiency

   This approach maintains O(n) time and handles reuse correctly.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Frequency map with counts is required for reuse scenarios [OK]

Hint: Frequency counts needed when characters can be reused infinitely [OK]

Common Mistakes:

• Assuming last seen indices suffice for reuse
• Thinking brute force is necessary

5. Suppose the problem is modified so that characters can be reused multiple times but you want the longest substring where each character appears at most twice. Which modification to the sliding window approach is correct?

hard

A. Use a hash set to track unique characters and reset the window whenever a duplicate is found

B. Use a dynamic programming approach storing max length substrings ending at each index

C. Use a brute force approach checking all substrings since sliding window cannot handle counts >1

D. Use a hash map to count occurrences of each character and shrink the window when any count exceeds 2

Solution

1. Step 1: Understand the new constraint

   Characters can appear at most twice, so we must track counts, not just presence.

2. Step 2: Modify sliding window

   Use a hash map to count occurrences. Expand right pointer, increment counts. When any count > 2, move left pointer and decrement counts until valid.

3. Step 3: Evaluate other options

   Hash set only tracks presence (not counts), brute force is inefficient, DP is not straightforward here.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Counting occurrences with sliding window handles "at most twice" constraint [OK]

Hint: Track counts, not just presence, for repeated allowed chars [OK]

Common Mistakes:

• Using hash set instead of counts
• Assuming sliding window can't handle counts >1