Jobs

Interviews

Discussions

Number of Zero-Filled Subarrays

Medium

Asked by:

14 views

Topics:

Arrays

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 <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Try coding it in LeetCode

Number of Zero-Filled Subarrays

Medium

Asked by:

14 views

Topics:

Arrays

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 <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible size of the input array?
Can the input array contain negative numbers or non-integer values?
What should be returned if the input array is null or empty?
Are overlapping subarrays counted multiple times? For example, in [0,0,0], is the subarray [0,0] counted twice, and the subarray [0] counted three times?
Is the input array read-only, or is it safe to modify it in place?

Brute Force Solution

Approach

The brute force method for counting zero-filled subarrays involves examining every possible group of numbers within the given sequence. We simply look at each possible starting point and length for a subarray. If the subarray only contains zeros, we increment our count; otherwise, we move on.

Here's how the algorithm would work step-by-step:

Begin by considering each position in the sequence as a potential starting point for a subarray.
For each starting point, consider all possible lengths of subarrays that could begin there.
Check if all numbers within the current subarray are equal to zero.
If every number is zero, then increase the total count of zero-filled subarrays by one.
If any number is not zero, then move to the next potential subarray to check.
After checking all possible subarrays starting from a given position, move on to the next position in the original sequence and repeat the process.
Continue this process until you have checked all possible subarrays that can be formed from the sequence.

Code Implementation

def number_of_zero_filled_subarrays_brute_force(numbers):
    number_of_zero_filled_subarrays = 0

    for start_index in range(len(numbers)):
        for end_index in range(start_index, len(numbers)):
            is_zero_filled = True

            # Check if the current subarray is all zeros
            for index in range(start_index, end_index + 1):
                if numbers[index] != 0:
                    is_zero_filled = False
                    break

            # Increment the counter if the subarray is zero-filled
            if is_zero_filled:
                number_of_zero_filled_subarrays += 1

    return number_of_zero_filled_subarrays

def number_of_zero_filled_subarrays(numbers):
    number_of_zero_filled_subarrays = 0
    current_zeros = 0

    for number in numbers:
        if number == 0:
            current_zeros += 1

            # Accumulate the number of zero filled subarrays
            number_of_zero_filled_subarrays += current_zeros
        else:
            # Reset the counter if a non-zero is encountered
            current_zeros = 0

    return number_of_zero_filled_subarrays

Big(O) Analysis

Time Complexity

O(n³) – The provided brute force approach iterates through all possible subarrays of the given array of size n. The outer loop iterates n times to select a starting index. The inner loop iterates up to n times to select an ending index for the subarray. Within the inner loop, we iterate through the selected subarray to check if all elements are zero, which takes up to n operations. Therefore, the overall time complexity is O(n * n * n) which simplifies to O(n³).

Space Complexity

O(1) – The provided brute force solution iterates through all possible subarrays using nested loops. It checks each subarray to see if it contains only zeros. This process doesn't involve creating any auxiliary data structures like lists, hash maps, or recursion. The algorithm solely uses a few variables to store indices and the count of zero-filled subarrays. Therefore, the auxiliary space used is constant and independent of the input array's size (N).

Optimal Solution

Approach

The key idea is to count consecutive zeros and use a formula to quickly calculate the number of zero-filled subarrays for each such sequence. By iterating through the given numbers and tracking these sequences, we efficiently compute the total number of zero-filled subarrays without redundant calculations.

Here's how the algorithm would work step-by-step:

Look at each number in the list one by one.
If you find a zero, start counting how many zeros are next to each other in a row.
If you find a non-zero number, stop counting the zeros.
Once you know how many zeros are in a row, use a simple calculation (like a formula) to figure out how many zero-filled groups you can make from that row. For example, if you have three zeros in a row (0, 0, 0), you can make six zero-filled subarrays: (0), (0), (0), (0, 0), (0, 0), (0, 0, 0).
Add the number of zero-filled groups you just calculated to a running total.
Start counting zeros again when you find another zero in the list.
Keep doing this until you've looked at every number in the list.
The final total is the answer.

Code Implementation

def number_of_zero_filled_subarrays(numbers):
    total_subarrays = 0
    consecutive_zeros_count = 0

    for number in numbers:
        if number == 0:
            # Increment count for consecutive zeros.
            consecutive_zeros_count += 1

        else:
            # Calculate subarrays and reset the count.
            total_subarrays += (consecutive_zeros_count * (consecutive_zeros_count + 1)) // 2

            # Reset count when encountering a non-zero.
            consecutive_zeros_count = 0

    # Add remaining subarrays after the loop.
    total_subarrays += (consecutive_zeros_count * (consecutive_zeros_count + 1)) // 2

    return total_subarrays

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums of size n exactly once. Inside the loop, it checks each element and updates a counter representing the consecutive zeros. The number of zero-filled subarrays is calculated based on this counter, which takes constant time. Therefore, the time complexity is directly proportional to the number of elements in the array, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm iterates through the input array and keeps track of the count of consecutive zeros using a single variable. It calculates the number of zero-filled subarrays based on this count and adds it to a running total, without needing any extra data structures that scale with the input size N (the number of elements in the input array). The space used for these variables (the count and the running total) remains constant, irrespective of the input size. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately since there are no subarrays.
Array with a single element which is zero	Return 1 as a single zero is a valid zero-filled subarray.
Array with a single element which is non-zero	Return 0 as there are no zero-filled subarrays.
Array containing only zeros	Calculate the sum of integers from 1 to the length of the array to represent all possible subarrays.
Array with alternating zeros and non-zeros	Correctly identify and count each individual zero-filled subarray sequence.
Array with a very long sequence of zeros (potential overflow)	Use a 64-bit integer type to store the counts of subarrays to prevent overflow.
Array with negative numbers	Negative numbers should not affect the logic, as only zeros are counted for subarrays.
Maximum sized input array with all zeros	Ensure the solution scales efficiently, avoiding unnecessary computations for large arrays, and uses 64-bit integers to store the result without overflow.

Null or empty input array

How to Handle:

Return 0 immediately since there are no subarrays.

Array with a single element which is zero

How to Handle:

Return 1 as a single zero is a valid zero-filled subarray.

Array with a single element which is non-zero

How to Handle:

Return 0 as there are no zero-filled subarrays.

Array containing only zeros

How to Handle:

Calculate the sum of integers from 1 to the length of the array to represent all possible subarrays.

Array with alternating zeros and non-zeros

How to Handle:

Correctly identify and count each individual zero-filled subarray sequence.

Array with a very long sequence of zeros (potential overflow)

How to Handle:

Use a 64-bit integer type to store the counts of subarrays to prevent overflow.

Array with negative numbers

How to Handle:

Negative numbers should not affect the logic, as only zeros are counted for subarrays.

Maximum sized input array with all zeros

How to Handle:

Ensure the solution scales efficiently, avoiding unnecessary computations for large arrays, and uses 64-bit integers to store the result without overflow.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible size of the input array?
Can the input array contain negative numbers or non-integer values?
What should be returned if the input array is null or empty?
Are overlapping subarrays counted multiple times? For example, in [0,0,0], is the subarray [0,0] counted twice, and the subarray [0] counted three times?
Is the input array read-only, or is it safe to modify it in place?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Begin by considering each position in the sequence as a potential starting point for a subarray.
For each starting point, consider all possible lengths of subarrays that could begin there.
Check if all numbers within the current subarray are equal to zero.
If every number is zero, then increase the total count of zero-filled subarrays by one.
If any number is not zero, then move to the next potential subarray to check.
After checking all possible subarrays starting from a given position, move on to the next position in the original sequence and repeat the process.
Continue this process until you have checked all possible subarrays that can be formed from the sequence.

Code Implementation

def number_of_zero_filled_subarrays_brute_force(numbers):
    number_of_zero_filled_subarrays = 0

    for start_index in range(len(numbers)):
        for end_index in range(start_index, len(numbers)):
            is_zero_filled = True

            # Check if the current subarray is all zeros
            for index in range(start_index, end_index + 1):
                if numbers[index] != 0:
                    is_zero_filled = False
                    break

            # Increment the counter if the subarray is zero-filled
            if is_zero_filled:
                number_of_zero_filled_subarrays += 1

    return number_of_zero_filled_subarrays

def number_of_zero_filled_subarrays(numbers):
    number_of_zero_filled_subarrays = 0
    current_zeros = 0

    for number in numbers:
        if number == 0:
            current_zeros += 1

            # Accumulate the number of zero filled subarrays
            number_of_zero_filled_subarrays += current_zeros
        else:
            # Reset the counter if a non-zero is encountered
            current_zeros = 0

    return number_of_zero_filled_subarrays

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Look at each number in the list one by one.
If you find a zero, start counting how many zeros are next to each other in a row.
If you find a non-zero number, stop counting the zeros.
Once you know how many zeros are in a row, use a simple calculation (like a formula) to figure out how many zero-filled groups you can make from that row. For example, if you have three zeros in a row (0, 0, 0), you can make six zero-filled subarrays: (0), (0), (0), (0, 0), (0, 0), (0, 0, 0).
Add the number of zero-filled groups you just calculated to a running total.
Start counting zeros again when you find another zero in the list.
Keep doing this until you've looked at every number in the list.
The final total is the answer.

Code Implementation

def number_of_zero_filled_subarrays(numbers):
    total_subarrays = 0
    consecutive_zeros_count = 0

    for number in numbers:
        if number == 0:
            # Increment count for consecutive zeros.
            consecutive_zeros_count += 1

        else:
            # Calculate subarrays and reset the count.
            total_subarrays += (consecutive_zeros_count * (consecutive_zeros_count + 1)) // 2

            # Reset count when encountering a non-zero.
            consecutive_zeros_count = 0

    # Add remaining subarrays after the loop.
    total_subarrays += (consecutive_zeros_count * (consecutive_zeros_count + 1)) // 2

    return total_subarrays

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 immediately since there are no subarrays.
Array with a single element which is zero	Return 1 as a single zero is a valid zero-filled subarray.
Array with a single element which is non-zero	Return 0 as there are no zero-filled subarrays.
Array containing only zeros	Calculate the sum of integers from 1 to the length of the array to represent all possible subarrays.
Array with alternating zeros and non-zeros	Correctly identify and count each individual zero-filled subarray sequence.
Array with a very long sequence of zeros (potential overflow)	Use a 64-bit integer type to store the counts of subarrays to prevent overflow.
Array with negative numbers	Negative numbers should not affect the logic, as only zeros are counted for subarrays.
Maximum sized input array with all zeros	Ensure the solution scales efficiently, avoiding unnecessary computations for large arrays, and uses 64-bit integers to store the result without overflow.

Null or empty input array

How to Handle:

Return 0 immediately since there are no subarrays.

Array with a single element which is zero

How to Handle:

Return 1 as a single zero is a valid zero-filled subarray.

Array with a single element which is non-zero

How to Handle:

Return 0 as there are no zero-filled subarrays.

Array containing only zeros

How to Handle:

Calculate the sum of integers from 1 to the length of the array to represent all possible subarrays.

Array with alternating zeros and non-zeros

How to Handle:

Correctly identify and count each individual zero-filled subarray sequence.

Array with a very long sequence of zeros (potential overflow)

How to Handle:

Use a 64-bit integer type to store the counts of subarrays to prevent overflow.

Array with negative numbers

How to Handle:

Negative numbers should not affect the logic, as only zeros are counted for subarrays.

Maximum sized input array with all zeros

How to Handle:

Ensure the solution scales efficiently, avoiding unnecessary computations for large arrays, and uses 64-bit integers to store the result without overflow.