2348. Number of Zero-Filled Subarrays
Problem Description
The problem requires us to find the total number of subarrays in a given integer array where every element is 0
. A subarray is defined as a contiguous sequence of elements within the array. This means that we are looking for all the continuous sequences of zeroes in the array and want to count them. It is important to realize that this includes subarrays of different lengths, starting and ending at any indices where zeros are contiguous.
Intuition
The intuition behind the solution approach is fairly straightforward. We want to iterate through the array and keep track of contiguous sequences of zeros. To achieve this, we can maintain a count (cnt
) that keeps track of the length of the current sequence of zeros we are in.
Starting from the beginning of the array, for each element, we check whether it is a zero:
- If it is, we increment our current zero sequence length count (
cnt
) by1
, since we've found an additional zero in our current subarray of zeros. - If it isn't, we reset our count to
0
as we're no longer in a sequence of zeros.
Now, the key insight is that each new zero we encounter not only forms a subarray of length 1
by itself but also extends the length of all subarrays ending at the previous zero by 1
. Therefore, at each step, we can add the current count of zeros to our answer (ans
).
For each new zero found, we do not need to recount all the subarrays it could create with all preceding zeros. We just realize that it extends them all by one. Thus, the current running cnt
can be added directly to ans
to account for all new subarrays ending at this zero.
This way, we effectively count all zero-filled subarrays without having to explicitly enumerate them all, leading to an efficient solution.
Learn more about Math patterns.
Solution Approach
The implemented solution relies on a simple linear scan of the input array, which implicitly tracks the size of contiguous zero-filled subarrays. Two main variables are introduced: ans
and cnt
. No additional data structures are needed, highlighting the simplicity and efficiency of the approach.
Let's delve deeper into the steps:
-
Initialize
ans
andcnt
to0
.ans
will keep the running total of all zero-filled subarray counts, whilecnt
will track the current number of zeros in a contiguous sequence. -
Iterate through each value
v
in thenums
array:a. If
v
is not0
, resetcnt
to0
. This step is important as it signifies that the current sequence of zeros has ended and any new sequence found later will be independent of any zeros previously encountered.b. If
v
is0
, incrementcnt
by1
, since we've found an additional zero that extends the current zero-filled subarray. -
After each iteration, add the value of
cnt
toans
. This is because every new zero found (or every zero in a contiguous sequence of zeros) not only represents a subarray of one element (itself) but also extends the length of any zero-filled subarray ending at the previous zero by one. Therefore,cnt
also represents the number of new zero-filled subarrays that the current0
contributes to. -
Continue this process until the end of the array.
-
Once the iteration is complete,
ans
will contain the total number of zero-filled subarrays in the array.
The time complexity of this approach is O(n), where n is the number of elements in the array, since it requires a single pass through the array. The space complexity is O(1), as the solution uses a constant amount of extra space.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach, let's use a small example with the array nums = [1, 0, 0, 2, 0]
.
-
Initialize
ans
andcnt
to0
. There are no zero-filled subarrays counted yet, and no current sequence of zeros. -
Start iterating through the
nums
array:- At the first element
1
,cnt
remains0
as it is not a zero. - At the second element
0
, incrementcnt
to1
. This zero forms a new subarray[0]
. Addcnt
toans
, soans
becomes1
. - At the third element
0
, incrementcnt
to2
. This zero extends the previous subarray to form a new one[0, 0]
and also makes an individual subarray[0]
. Addcnt
toans
, soans
becomes1 + 2 = 3
. - At the fourth element
2
, resetcnt
to0
as the sequence of zeros has been broken. - At the fifth element
0
, incrementcnt
to1
. This zero forms a new subarray[0]
. Addcnt
toans
, soans
becomes3 + 1 = 4
.
- At the first element
-
By the end of the array, we've counted all zero-filled subarrays:
[0]
,[0, 0]
, and two separate[0]
subarrays after the2
. Therefore, the total number of zero-filled subarrays in this example is4
.
Thus, ans
holds the correct total, and the process demonstrates both the resetting of cnt
when non-zero elements are encountered and the accumulation of the number of subarrays in ans
as zero elements are processed. The approach ensures we count consecutive sequences of zeros efficiently without unnecessary enumeration.
Solution Implementation
1from typing import List
2
3class Solution:
4 def zero_filled_subarray(self, nums: List[int]) -> int:
5 # Initialize the counter for current zero sequence and the answer accumulator
6 current_zero_count = total_subarrays = 0
7
8 # Iterate over each number in the input list
9 for num in nums:
10 if num == 0:
11 # If the current number is zero, increment the current zero sequence counter
12 current_zero_count += 1
13 else:
14 # If the current number is not zero, reset the counter
15 current_zero_count = 0
16
17 # Add the current zero sequence length to the total number of subarrays
18 # This works because for each new zero, there are `current_zero_count` new subarrays ending with that zero
19 total_subarrays += current_zero_count
20
21 # Return the total count of zero-filled subarrays
22 return total_subarrays
23
1class Solution {
2 // Method to calculate the number of zero-filled contiguous subarrays
3 public long zeroFilledSubarray(int[] nums) {
4 long totalCount = 0; // Initialize total count of zero-filled subarrays
5 int zeroCount = 0; // Initialize count of consecutive zeros
6
7 // Iterate through the array elements
8 for (int value : nums) {
9 // Reset zeroCount to 0 if the current element is not zero
10 // Otherwise, increment zeroCount
11 zeroCount = (value != 0) ? 0 : zeroCount + 1;
12 // Add the current zeroCount to the total count
13 totalCount += zeroCount;
14 }
15
16 return totalCount; // Return the total count of zero-filled subarrays
17 }
18}
19
1class Solution {
2public:
3 // Function to calculate the number of zero-filled subarrays.
4 long long zeroFilledSubarray(vector<int>& nums) {
5 long long answer = 0; // Variable to store the final answer.
6 int zeroCount = 0; // Counter to keep track of consecutive zeros.
7
8 // Iterate through the numbers in the vector.
9 for (int value : nums) {
10 // Reset the counter if the current value is not zero, otherwise increase it.
11 zeroCount = (value != 0) ? 0 : zeroCount + 1;
12
13 // Add the number of new zero-filled subarrays ending with the current value.
14 answer += zeroCount;
15 }
16
17 // Return the total number of zero-filled subarrays found.
18 return answer;
19 }
20};
21
1function zeroFilledSubarray(nums: number[]): number {
2 let totalSubarrays = 0; // This variable will hold the total count of zero-filled subarrays
3 let currentZerosCount = 0; // This variable tracks the current consecutive zeros count
4
5 // Loop through each number in the nums array
6 for (const value of nums) {
7 if (value === 0) {
8 // If the current value is zero, increment the current consecutive zeros count
9 currentZerosCount++;
10 } else {
11 // If it's not zero, reset the count to 0
12 currentZerosCount = 0;
13 }
14 // Add the currentZerosCount to the total subarrays count which also includes
15 // all subarrays ending with the current element
16 totalSubarrays += currentZerosCount;
17 }
18
19 // Return the total number of zero-filled subarrays found in the nums array
20 return totalSubarrays;
21}
22
Time and Space Complexity
The provided code snippet has a time complexity of O(n)
, where n
is the length of the input list nums
. This is because the code iterates through the list once, performing a constant number of operations for each element.
The space complexity of this code is O(1)
. No additional space proportional to the input size is used; the variables ans
and cnt
use a fixed amount of space regardless of the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement priority queue?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first