Binary Subarrays With Sum

Binary Subarrays With Sum

What is this problem about?

The "Binary Subarrays With Sum interview question" is a counting problem. You are given a binary array (containing only 0s and 1s) and a target goal. You need to find the total number of non-empty subarrays that have a sum equal to goal. This is a specific variation of the "Subarray Sum Equals K" problem, optimized for binary inputs.

Why is this asked in interviews?

Companies like Meta, Amazon, and Google use the "Binary Subarrays With Sum coding problem" to test a candidate's mastery of the Sliding Window and Prefix Sum techniques. It evaluates if you can solve a problem in $O(N)$ time and $O(1)$ or $O(N)$ space. It’s a great test of "Hash Table interview pattern" for tracking frequency.

Algorithmic pattern used

There are two primary ways to solve this:

1. Prefix Sum + Hash Map:
   • Keep a running current_sum.
   • Use a hash map to store how many times each prefix sum has occurred.
   • For every index, the number of subarrays ending there with sum goal is map[current_sum - goal].
2. Three Pointers (Sliding Window):
   • For binary arrays, the sum is monotonic (it never decreases).
   • You can use a sliding window to find the number of subarrays with sum at most goal and subtract the number of subarrays with sum at most goal-1.

Example explanation

Array: [1, 0, 1, 0, 1], Goal: 2

• Using Prefix Sum Map:
  • sums: 0:1 (initial)
  • index 0 (1): sum=1. Need 1-2 = -1. Map: {0:1, 1:1}
  • index 1 (0): sum=1. Need 1-2 = -1. Map: {0:1, 1:2}
  • index 2 (1): sum=2. Need 2-2 = 0. map[0] is 1. Count = 1. Map: {0:1, 1:2, 2:1}
  • index 3 (0): sum=2. Need 2-2 = 0. map[0] is 1. Count = 2. Map: {0:1, 1:2, 2:2} ... and so on.

Common mistakes candidates make

• $O(N^2)$ Brute Force: Checking every possible subarray sum.
• Handling Zero: Failing to correctly count subarrays when goal = 0. Subarrays like [0, 0] have many sub-segments that sum to zero.
• Map Initialization: Forgetting to initialize the map with {0: 1} to account for subarrays that start from the beginning of the array.

Interview preparation tip

Master the "At Most K" trick for sliding windows. Finding "Exactly K" is often countAtMost(K) - countAtMost(K-1). This is a powerful "Sliding Window interview pattern" that simplifies many subarray problems.