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.
For example:
nums = [1, 3, 0, 0, 2, 0, 0, 4]
should return 6.
[0]
as a subarray.[0, 0]
as a subarray.nums = [0, 0, 0, 2, 0, 0]
should return 9.
[0]
as a subarray.[0, 0]
as a subarray.[0, 0, 0]
as a subarray.nums = [2, 10, 2019]
should return 0.
What is the most efficient way to accomplish this, what is the Big(O) run-time, and what is the Big(O) space usage?
A naive approach would be to iterate through all possible subarrays and count those that contain only zeros. For each subarray, we check if all elements are zero, and if so, increment our counter.
def count_zero_subarrays_brute_force(nums):
count = 0
n = len(nums)
for i in range(n):
for j in range(i, n):
subarray = nums[i:j+1]
if all(x == 0 for x in subarray):
count += 1
return count
The time complexity is O(n^3) because there are O(n^2) possible subarrays, and checking if a subarray contains only zeros takes O(n) time.
The space complexity is O(n) in the worst case for storing the subarray.
A more efficient approach is to iterate through the array and keep track of the consecutive zeros. When we encounter a non-zero element, we can calculate the number of subarrays formed by the previous consecutive zeros using the formula n * (n + 1) / 2
, where n
is the number of consecutive zeros. Then, reset the consecutive zero counter.
def count_zero_subarrays_optimal(nums):
count = 0
consecutive_zeros = 0
for num in nums:
if num == 0:
consecutive_zeros += 1
else:
count += consecutive_zeros * (consecutive_zeros + 1) // 2
consecutive_zeros = 0
count += consecutive_zeros * (consecutive_zeros + 1) // 2 # Handle trailing zeros
return count
The time complexity is O(n) because we iterate through the array only once.
The space complexity is O(1) because we only use a constant amount of extra space.
n * (n + 1) / 2
.For nums = [0, 0, 0, 2, 0, 0]
, the function would work as follows:
consecutive_zeros = 0
, count = 0
num = 0
: consecutive_zeros = 1
num = 0
: consecutive_zeros = 2
num = 0
: consecutive_zeros = 3
num = 2
: count = 3 * (3 + 1) // 2 = 6
, consecutive_zeros = 0
num = 0
: consecutive_zeros = 1
num = 0
: consecutive_zeros = 2
count = 6 + 2 * (2 + 1) // 2 = 6 + 3 = 9
The function returns 9.