# 14.03.2024 [930. Binary Subarrays With Sum]
Count `goal`-sum subarrays in a `0-1` array #medium
14.03.2024
930. Binary Subarrays With Sum medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/538
Problem TLDR
Count goal
-sum subarrays in a 0-1
array #medium
Intuition
Let’s observe an example:
// [0,0,1,0,1,0,0,0]
//1 * * *
//2 *
//3 * *
//4 *
//5 * *
//6 * * *
//7 * *
//8 * * *
//9 * * *
//10* * * *
//11 * * * *
//12* * * * *
// 1 + 2 + 3 + 2*3
As we count possible subarrays, we see that zeros suffix and prefix matters and we can derive the math formula for them.
The corner case is an all-zero array: we just take an arithmetic progression sum.
Approach
careful with pointers, widen zeros in a separate step
use a separate variables to count zeros
move pointers only forward
check yourself on the corner cases
0, 0
and0, 0, 1
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun numSubarraysWithSum(nums: IntArray, goal: Int): Int {
var i = 0; var j = 0; var sum = 0; var res = 0
while (i < nums.size) {
sum += nums[i]
while (sum > goal && j < i) sum -= nums[j++]
if (sum == goal) {
var z1 = 0
while (i + 1 < nums.size && nums[i + 1] == 0) { i++; z1++ }
res += if (goal == 0) (z1 + 1) * (z1 + 2) / 2 else {
var z2 = 0
while (j < i && nums[j] == 0) { j++; z2++ }
1 + z1 + z2 + z1 * z2
}
}; i++
}; return res
}
pub fn num_subarrays_with_sum(nums: Vec<i32>, goal: i32) -> i32 {
let (mut i, mut j, mut sum, mut res) = (0, 0, 0, 0);
while i < nums.len() {
sum += nums[i];
while sum > goal && j < i { sum -= nums[j]; j += 1 }
if sum == goal {
let mut z1 = 0;
while i + 1 < nums.len() && nums[i + 1] == 0 { i += 1; z1 += 1 }
res += if goal == 0 { (z1 + 1) * (z1 + 2) / 2 } else {
let mut z2 = 0;
while j < i && nums[j] == 0 { j += 1; z2 += 1 }
1 + z1 + z2 + z1 * z2
}
}; i += 1
}; res
}