Number of Zero-Filled Subarrays
MedPrompt
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:
Input: nums = [1,3,0,0,2,0,0,4]
Output: 6
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:
Input: nums = [0,0,0,2,0,0]
Output: 9
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:
Input: nums = [2,10,2019]
Output: 0
Explanation: There is no subarray filled with 0. Therefore, we return 0.
Constraints:
1 <= nums.length <= 105-109 <= nums[i] <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves iterating through all possible subarrays, checking if each one is filled with zeros, and counting them. We can use two nested loops. The outer loop fixes the starting point of a subarray, and the inner loop extends the subarray to the right, counting valid zero-filled subarrays as it goes.
Algorithm
- Initialize a
longvariablecountto0to store the total number of zero-filled subarrays. - Use a nested loop structure. The outer loop iterates from
i = 0ton-1, wherenis the length of the array. The indexirepresents the starting point of a subarray. - The inner loop iterates from
j = iton-1. The indexjrepresents the ending point of the subarray. - For each subarray defined by
[i, j], check if the elementnums[j]is0. - If
nums[j]is0, it means the subarray fromitojconsists only of zeros (because all previous elements fromitoj-1must also have been zero for the inner loop to continue this far). Increment thecount. - If
nums[j]is not0, it means the current subarray and any subsequent subarrays starting aticannot be zero-filled. Therefore,breakthe inner loop and proceed to the next starting indexi+1. - After both loops complete, return the final
count.
Walkthrough
The brute-force method systematically checks every possible contiguous subarray within the input array nums. We can implement this using two nested loops. The outer loop, with index i, selects the starting element of the subarray. The inner loop, with index j, extends the subarray from i to j.
For each starting position i, we iterate from j = i onwards. If nums[j] is 0, we have found a valid zero-filled subarray nums[i...j], so we increment our total count. If we encounter a non-zero element at nums[j], we know that no subarray starting at i and ending at or after j can be zero-filled. This allows us to break the inner loop and move to the next starting position i+1, providing a slight optimization over a naive three-loop approach.
class Solution { public long zeroFilledSubarray(int[] nums) { long count = 0; int n = nums.length; for (int i = 0; i < n; i++) { // Start a new potential subarray at index i for (int j = i; j < n; j++) { // Extend the subarray to index j if (nums[j] == 0) { // If nums[j] is 0, the subarray nums[i...j] is valid count++; } else { // If we find a non-zero, no more valid subarrays can start at i break; } } } return count; }}While straightforward, this approach is computationally expensive as it re-evaluates parts of the array multiple times.
Complexity
Time
O(n^2), where `n` is the length of the `nums` array. In the worst-case scenario, such as an array filled entirely with zeros, the inner loop runs `n-i` times for each `i`. This results in a total number of operations proportional to `n + (n-1) + ... + 1`, which is `n * (n+1) / 2`, leading to a quadratic time complexity.
Space
O(1), as we only use a constant amount of extra space for loop indices and the counter.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the definition of a subarray.
Cons
Highly inefficient for large inputs due to its quadratic time complexity.
Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints (
n <= 10^5).
Solutions
Solution
class Solution {public long zeroFilledSubarray(int[] nums) { long ans = 0; int cnt = 0; for (int v : nums) { cnt = v != 0 ? 0 : cnt + 1; ans += cnt; } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.