Binary Subarrays With Sum

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given a binary array nums (containing only 0s and 1s) and an integer goal. Your task is to find the total number of non-empty subarrays whose elements sum up to the goal.

A subarray is a contiguous part of the array.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer N, the number of elements in the array.

The second line contains the integer goal.

The third line contains N space-separated integers, representing the elements of the nums array.

Output Format:

Your function should return a single integer representing the total count of valid subarrays. The runner code will handle printing.

Notes:

A brute-force solution that checks the sum of all possible O(N^2) subarrays will be too slow for the given constraints. An efficient O(N) solution is required. This can be achieved using a hash map to store the frequencies of prefix sums encountered so far.

Sample Input 1:

5
2
1 0 1 0 1

Sample Output 1:

Explanation for Sample 1:

The 4 subarrays that sum to 2 are:
    [1, 0, 1] (from index 0 to 2)
    [1, 0, 1, 0] (from index 0 to 3)
    [0, 1, 0, 1] (from index 1 to 4)
    [1, 0, 1] (from index 2 to 4)

Sample Input 2:

5
0
0 0 0 0 0

Sample Output 2:

Explanation for Sample 2:

Any subarray consisting only of 0s will have a sum of 0. The number of non-empty subarrays in an array of size 5 is 5 * (5 + 1) / 2 = 15.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

1 <= nums.length <= 3 * 10^4
nums[i] is either 0 or 1.
0 <= goal <= nums.length
Time Limit: 1 sec

Approaches (1)

Approach 1

Sliding window

Time Complexity

Space Complexity

(100% EXP penalty)

Binary Subarrays With Sum

Console