Jobs

Interviews

Discussions

Duplicate Zeros

Easy

Amazon

2 views

Topics:

Arrays

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything.

Example 1:

Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Example 2:

Input: arr = [1,2,3]
Output: [1,2,3]
Explanation: After calling your function, the input array is modified to: [1,2,3]

Constraints:

1 <= arr.length <= 10⁴
0 <= arr[i] <= 9

Duplicate Zeros

Easy

Amazon

2 views

Topics:

Arrays

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything.

Example 1:

Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Example 2:

Input: arr = [1,2,3]
Output: [1,2,3]
Explanation: After calling your function, the input array is modified to: [1,2,3]

Constraints:

1 <= arr.length <= 10⁴
0 <= arr[i] <= 9

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 expected behavior if the array contains multiple consecutive zeros?
Can the input array be empty or null?
Are the numbers in the array integers? What is the range of possible integer values?
Should the modifications be done in-place, modifying the original array directly, or should I return a new array?
What happens if duplicating the zeros causes the array to overflow (i.e., exceed its original size)? Should I truncate the elements at the end?

Brute Force Solution

Approach

The brute force approach directly simulates the duplication process. We go through the numbers one by one, and when we see a zero, we insert another zero right after it, shifting everything else down.

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

Look at the first number.
If it's a zero, add another zero right after it and move everything else down to make space.
If it's not a zero, just move on to the next number.
Keep doing this for each number until you reach the end.

Code Implementation

def duplicate_zeros(numbers):
    index = 0
    while index < len(numbers):
        # Found a zero, need to insert another
        if numbers[index] == 0:

            # Shift elements to the right to make space
            for element_index in range(len(numbers) - 1, index, -1):
                numbers[element_index] = numbers[element_index - 1]

            # Protect against array overflow and duplicate the zero.
            if index + 1 < len(numbers):
                numbers[index + 1] = 0

            # Move past the duplicated zero.
            index += 2

        # Keep traversing to find the next zero.
        else:
            index += 1

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach iterates through the input array of size n. When a zero is encountered, the algorithm inserts another zero and shifts the subsequent elements to the right. Shifting elements involves iterating from the end of the array segment down to the insertion point, potentially requiring up to n operations in the worst case for each zero found. Therefore, in the worst-case scenario where there are many zeros, the shifting operation is performed close to n times for each zero, leading to O(n*n) or O(n²) time complexity. The time complexity is dominated by the shifting operation within the loop.

Space Complexity

O(N) – The brute force approach described involves inserting elements into the array, which, without further constraints or in-place optimizations, conceptually creates a new array or requires shifting existing elements. Although the description does not explicitly state a *new* array is created, the action of inserting and shifting implies auxiliary space proportional to the number of elements that are potentially shifted or duplicated. In the worst-case scenario, where the input array `arr` contains many zeros, the space needed to accommodate the duplicated zeros could approach the size of the input array, N. Thus, the auxiliary space complexity is O(N), where N is the length of the input array.

Optimal Solution

Approach

The most efficient way to handle this problem involves working backward to avoid constantly shifting elements. First, we determine the final size of the modified list, and then we fill it from the end toward the start.

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

First, count how many zeros are in the original list because each zero will become two zeros in the modified list.
Calculate how long the new list needs to be. This will be the original list length plus the number of zeros.
Start writing to the list from the end. If you encounter a non-zero number, simply copy it to its new position at the end of the expanded list.
If you find a zero, write two zeros to the end of the expanded list (decrementing the write pointer twice) to duplicate it, handling the case where you reach the beginning of the array.
Continue moving backwards until you reach the beginning of the original list. You've now effectively duplicated all the zeros while avoiding unnecessary shifts.

Code Implementation

def duplicate_zeros(array):
    number_of_zeros = array.count(0)

    expanded_array_length = len(array) + number_of_zeros

    last_element_index = len(array) - 1
    expanded_array_last_index = expanded_array_length - 1

    # Iterate from the end of the original array to the beginning
    while last_element_index >= 0:
        if expanded_array_last_index > last_element_index:

            # Copy non-zero elements to the end of the expanded array
            if array[last_element_index] != 0:
                if expanded_array_last_index < len(array):
                    array[expanded_array_last_index] = array[last_element_index]

                expanded_array_last_index -= 1

            # Duplicate zeros, adjusting array indices as needed
            else:
                if expanded_array_last_index < len(array):
                    array[expanded_array_last_index] = 0

                expanded_array_last_index -= 1

                if expanded_array_last_index < len(array):
                    array[expanded_array_last_index] = 0

                expanded_array_last_index -= 1

        else:
            # When expanded_array_last_index == last_element_index, early termination
            break

        last_element_index -= 1

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n twice. First, it counts the number of zeros, iterating through all n elements. Second, it iterates backward through the potentially modified array (which can be at most 2n in size but scales directly with the original input n) to duplicate zeros. Therefore, the total number of operations is proportional to n, leading to a time complexity of O(n).

Space Complexity

O(1) – The algorithm operates in-place, modifying the original list directly. It uses a few integer variables to keep track of positions while iterating backward through the array. The number of variables does not depend on the size of the input array, N. Therefore, the auxiliary space used is constant, resulting in a space complexity of O(1).

Edge Cases

Case	How to Handle
Null or empty array input	Return immediately or throw an IllegalArgumentException, depending on requirements.
Array with only one element	The algorithm should handle this as there are no duplicates to process and the array remains unchanged.
Array with all zeros	The algorithm should correctly expand the array, effectively doubling the number of zeros.
Array with no zeros	The algorithm should complete without modification as there's nothing to duplicate.
Array filled with zeros, nearing maximum size allowed	Ensure the algorithm does not exceed memory constraints when expanding the array, causing an out-of-memory error.
Array with zeros at the end	The insertion logic must handle overwriting existing trailing elements correctly.
Integer overflow when calculating array indices or resizing	Use appropriate data types (e.g., long) for calculations to avoid integer overflow errors during array manipulation.
Very large array size close to allowed maximum	Verify that algorithm runtime is acceptable for the large input array, especially if using shifting operations.

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 expected behavior if the array contains multiple consecutive zeros?
Can the input array be empty or null?
Are the numbers in the array integers? What is the range of possible integer values?
Should the modifications be done in-place, modifying the original array directly, or should I return a new array?
What happens if duplicating the zeros causes the array to overflow (i.e., exceed its original size)? Should I truncate the elements at the end?

Brute Force Solution

Approach

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

Look at the first number.
If it's a zero, add another zero right after it and move everything else down to make space.
If it's not a zero, just move on to the next number.
Keep doing this for each number until you reach the end.

Code Implementation

def duplicate_zeros(numbers):
    index = 0
    while index < len(numbers):
        # Found a zero, need to insert another
        if numbers[index] == 0:

            # Shift elements to the right to make space
            for element_index in range(len(numbers) - 1, index, -1):
                numbers[element_index] = numbers[element_index - 1]

            # Protect against array overflow and duplicate the zero.
            if index + 1 < len(numbers):
                numbers[index + 1] = 0

            # Move past the duplicated zero.
            index += 2

        # Keep traversing to find the next zero.
        else:
            index += 1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, count how many zeros are in the original list because each zero will become two zeros in the modified list.
Calculate how long the new list needs to be. This will be the original list length plus the number of zeros.
Start writing to the list from the end. If you encounter a non-zero number, simply copy it to its new position at the end of the expanded list.
If you find a zero, write two zeros to the end of the expanded list (decrementing the write pointer twice) to duplicate it, handling the case where you reach the beginning of the array.
Continue moving backwards until you reach the beginning of the original list. You've now effectively duplicated all the zeros while avoiding unnecessary shifts.

Code Implementation

def duplicate_zeros(array):
    number_of_zeros = array.count(0)

    expanded_array_length = len(array) + number_of_zeros

    last_element_index = len(array) - 1
    expanded_array_last_index = expanded_array_length - 1

    # Iterate from the end of the original array to the beginning
    while last_element_index >= 0:
        if expanded_array_last_index > last_element_index:

            # Copy non-zero elements to the end of the expanded array
            if array[last_element_index] != 0:
                if expanded_array_last_index < len(array):
                    array[expanded_array_last_index] = array[last_element_index]

                expanded_array_last_index -= 1

            # Duplicate zeros, adjusting array indices as needed
            else:
                if expanded_array_last_index < len(array):
                    array[expanded_array_last_index] = 0

                expanded_array_last_index -= 1

                if expanded_array_last_index < len(array):
                    array[expanded_array_last_index] = 0

                expanded_array_last_index -= 1

        else:
            # When expanded_array_last_index == last_element_index, early termination
            break

        last_element_index -= 1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty array input	Return immediately or throw an IllegalArgumentException, depending on requirements.
Array with only one element	The algorithm should handle this as there are no duplicates to process and the array remains unchanged.
Array with all zeros	The algorithm should correctly expand the array, effectively doubling the number of zeros.
Array with no zeros	The algorithm should complete without modification as there's nothing to duplicate.
Array filled with zeros, nearing maximum size allowed	Ensure the algorithm does not exceed memory constraints when expanding the array, causing an out-of-memory error.
Array with zeros at the end	The insertion logic must handle overwriting existing trailing elements correctly.
Integer overflow when calculating array indices or resizing	Use appropriate data types (e.g., long) for calculations to avoid integer overflow errors during array manipulation.
Very large array size close to allowed maximum	Verify that algorithm runtime is acceptable for the large input array, especially if using shifting operations.