Binary Subarrays With Sum - Practice Coding Problems

Binary Subarrays With Sum - Problem

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.

For example, if nums = [1,0,1,0,1] and goal = 2, we need to find all subarrays that sum to 2: [1,0,1], [0,1,0,1], and [1,0,1] (at different positions).

Input & Output

Example 1 — Basic Binary Array

$ Input: nums = [1,0,1,0,1], goal = 2

› Output: 4

💡 Note: Four subarrays have sum 2: [1,0,1] at index 0-2, [0,1,0,1] at index 1-4, [1,0,1] at index 2-4, and [0,1] at index 3-4

Example 2 — All Ones

$ Input: nums = [1,1,1], goal = 2

› Output: 2

💡 Note: Two subarrays have sum 2: [1,1] at index 0-1 and [1,1] at index 1-2

Example 3 — Goal Zero

$ Input: nums = [0,0,0,0,0], goal = 0

› Output: 15

💡 Note: All possible subarrays of zeros sum to 0. With 5 elements, there are 5*6/2 = 15 total subarrays

Constraints

1 ≤ nums.length ≤ 3 × 10⁴
nums[i] is either 0 or 1
0 ≤ goal ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Binary array [1,0,1,0,1] with goal=2

Process

Find all contiguous subarrays that sum to goal

Output

Count of valid subarrays = 4

Key Takeaway

🎯 Key Insight: Use prefix sums to transform the problem into finding pairs of sums that differ by goal

Asked in

F Facebook 25 G Google 20 a Amazon 15

The key insight is using prefix sums with a hash map to efficiently count subarrays. For each position, we check if (current_sum - goal) exists in our history. Best approach uses prefix sum + HashMap in O(n) time, O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window (At Most Technique)	O(n)	O(1)	Use atMost(goal) - atMost(goal-1) to get exactly goal subarrays
Brute Force - Check All Subarrays	O(n²)	O(1)	Generate all possible subarrays and count those with sum equal to goal
Prefix Sum with HashMap	O(n)	O(n)	Use prefix sums and hash map to find subarrays with target sum in one pass

Sliding Window (At Most Technique) — Algorithm Steps

Create helper function atMost(k) using sliding window
Count subarrays with sum ≤ k
Return atMost(goal) - atMost(goal-1)

Visualization

Tap to expand

Step-by-Step Walkthrough

AtMost(2)

Count subarrays with sum ≤ 2

AtMost(1)

Count subarrays with sum ≤ 1

Subtract

Difference gives exactly 2

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int atMost(int* nums, int numsSize, int k) {
    if (k < 0) return 0;
    
    int left = 0;
    int count = 0;
    int currentSum = 0;
    
    for (int right = 0; right < numsSize; right++) {
        currentSum += nums[right];
        
        while (currentSum > k) {
            currentSum -= nums[left];
            left++;
        }
        
        count += right - left + 1;
    }
    
    return count;
}

int solution(int* nums, int numsSize, int goal) {
    return atMost(nums, numsSize, goal) - atMost(nums, numsSize, goal - 1);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[30000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int goal;
    scanf("%d", &goal);
    
    int result = solution(nums, numsSize, goal);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes of sliding window, each taking O(n) time

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for window pointers

✓ Linear Space

67.0K Views

Medium Frequency

~25 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window (At Most Technique) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler