Number of Zero-Filled Subarrays
Problem Description
Given an integer array nums, return the number of subarrays filled with 0.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Explanation:
- There are 4 occurrences of [0] as a subarray.
- There are 2 occurrences of [0,0] as a subarray.
- There is no occurrence of a subarray with a size more than 2 filled with 0. Therefore, we return 6.
Example 2:
Explanation:
- There are 5 occurrences of [0] as a subarray.
- There are 3 occurrences of [0,0] as a subarray.
- There is 1 occurrence of [0,0,0] as a subarray.
- There is no occurrence of a subarray with a size more than 3 filled with 0. Therefore, we return 9.
Example 3:
Explanation: There is no subarray filled with 0. Therefore, we return 0.
Constraints:
- 1 <= nums.length <= 105
- -109 <= nums[i] <= 109
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The simplest approach to solve this problem is to consider all possible subarrays and count those filled entirely with zeroes. While this method is straightforward, it can be inefficient for large arrays due to the sheer number of potential subarrays.
Steps:
- Iterate over all possible starting points of subarrays.
- For each starting point, extend the subarray endpoint till we are passing zeroes.
- Count the subarrays when a complete run of zeroes is detected.
Code:
- Time Complexity: O(n^2) - As we check each subarray which takes quadratic time.
- Space Complexity: O(1) - No additional space is used beyond input size.
2. Optimized Linear Scan
Intuition:
We can achieve a more optimal solution by recognizing runs of zeroes as we iterate over the array. For each segment of contiguous zeroes, the number of zero-filled subarrays can be calculated using combinatorial arithmetic.
Specifically, a contiguous run of k zeroes contributes k * (k + 1) / 2 zero-filled subarrays.
Steps:
- Initialize a counter for zero segments (
zeroCount) and the total result (result). - Traverse the array.
- For every zero encountered, increase the
zeroCount. - If a non-zero is encountered or the array ends, add the count of zero-filled subarrays for the segment, i.e.,
zeroCount * (zeroCount + 1) / 2to the result, and resetzeroCount. - Return the result.
Code:
- Time Complexity: O(n) - We pass through the array a single time.
- Space Complexity: O(1) - Only a constant amount of extra space is used.