Jobs

Interviews

Discussions

Duplicate Zeros

Easy

Asked by:

More companies

49 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

Try coding it in LeetCode

Duplicate Zeros

Easy

Asked by:

49 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

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 range of values for the integers in the input array?
What should happen if the array is empty or null?
Can I assume the array will always have enough space to accommodate the duplicated zeros, or might the duplication truncate the array at the end?
Are we optimizing for space complexity in addition to time complexity?
Could you provide an example input and the corresponding modified output array?

Brute Force Solution

Approach

The core idea is to carefully simulate the duplication process. We'll create a brand new container and copy elements one by one from the original, inserting extra zeros whenever we find one in the original.

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

Make a fresh, empty container that is exactly the same size as the original.
Start looking at the first spot in the original container.
Copy whatever you find there into the first empty spot in the new container.
Now, here's the key: If the thing you just copied was a zero, then immediately put another zero in the next empty spot of the new container.
Move to the next thing in the original container and repeat the copying process.
Keep doing this until you've looked at everything in the original container.
If, while adding elements to the new container, you reach the end before you've looked at everything in the original container, then stop filling the new container.
Finally, replace the original container with the contents of this brand new container.

Code Implementation

def duplicate_zeros_brute_force(original_array):
    new_array = [0] * len(original_array)
    new_array_index = 0
    original_array_index = 0

    # Iterate through the original array until we reach the end
    while original_array_index < len(original_array):
        # Copy the element from the original to the new array
        new_array[new_array_index] = original_array[original_array_index]
        new_array_index += 1

        # Check if we've reached the end of the new array
        if new_array_index == len(new_array):
            break

        # If we encounter a zero, duplicate it in the new array
        if original_array[original_array_index] == 0:

            new_array[new_array_index] = 0

            new_array_index += 1

            # Ensure that we are still within the bounds of the new array
            if new_array_index == len(new_array):
                break

        original_array_index += 1

    # Replace the original array with the modified new array
    for index in range(len(original_array)):
        original_array[index] = new_array[index]

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n exactly once. Inside the loop, it copies each element to a new array and potentially inserts an additional zero. While the insertion of a zero appears as another operation, it still happens within the scope of a single iteration of the main loop and on specific conditions (when a zero is encountered). Therefore, the number of operations scales linearly with the size of the input array n. Thus the time complexity is O(n).

Space Complexity

O(N) – The algorithm creates a new container (array) of the same size as the original, where N is the size of the original array. This new array is used to store the modified contents with the duplicated zeros. Therefore, the auxiliary space used is directly proportional to the size of the input array, resulting in a space complexity of O(N).

Optimal Solution

Approach

The most efficient way to solve this is by working backwards. We figure out how big the final modified list will be and then adjust the original list from the end towards the beginning to avoid messing up parts we haven't touched yet.

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

First, count how many zeros are in the original list.
Then, determine the final size of the modified list by adding the number of zeros to the original size of the list.
Now, start filling in the modified list by working backwards from the end of the original list.
If you encounter a zero while going backwards, copy it into the modified list, then copy another zero immediately before it. Decrement the counter/position twice to account for the added zero.
If you encounter a number other than zero, just copy it into the modified list. Decrement the counter/position once.
If the modified list size is larger than the original list size, stop copying once you reach the beginning of the original list.

Code Implementation

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

    modified_array_length = len(array) + number_of_zeros

    original_array_length = len(array)

    # Traverse backwards to modify in place.
    current_index = original_array_length - 1
    modified_index = modified_array_length - 1

    while current_index >= 0 and modified_index >= 0:

        if array[current_index] == 0:
            # If we encounter a zero, duplicate it.
            if modified_index < original_array_length:
                array[modified_index] = 0
            modified_index -= 1
            if modified_index < original_array_length:
                array[modified_index] = 0
        else:
            # Copy non-zero elements directly.
            if modified_index < original_array_length:
                array[modified_index] = array[current_index]

        modified_index -= 1
        current_index -= 1

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array once to count the number of zeros. It then iterates through the array again, backwards, to modify it in place. Each element in the input array of size 'n' is visited at most a constant number of times (twice, once to count zeros and once to modify the array). Therefore, the time complexity is directly proportional to the size of the input array, resulting in O(n).

Space Complexity

O(1) – The provided algorithm modifies the input list in-place. It uses a fixed number of integer variables to keep track of the number of zeros, the adjusted length, and the current positions while iterating backwards through the array. Since the memory used by these variables doesn't depend on the size N of the input array, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty array	Return immediately without any processing to avoid NullPointerException or other errors.
Array containing only zeros	The algorithm correctly duplicates each zero, shifting the existing zeros to the right.
Array without any zeros	The algorithm does nothing, correctly leaving the array unchanged.
Array with a zero at the end	The algorithm correctly duplicates the zero, shifting the last element off the end.
Array with a zero at the beginning	The algorithm duplicates the zero and shifts all other elements to the right.
Array close to full capacity, with several zeros near the end	The algorithm handles this correctly, truncating any elements that go beyond the array length.
Array containing negative numbers and zeros	The algorithm only duplicates zeros and is not affected by negative numbers.
Large array with many zeros scattered throughout	The in-place modification ensures memory usage is efficient, handling large arrays without significant overhead.

Null or empty array

How to Handle:

Return immediately without any processing to avoid NullPointerException or other errors.

Array containing only zeros

How to Handle:

The algorithm correctly duplicates each zero, shifting the existing zeros to the right.

Array without any zeros

How to Handle:

The algorithm does nothing, correctly leaving the array unchanged.

Array with a zero at the end

How to Handle:

The algorithm correctly duplicates the zero, shifting the last element off the end.

Array with a zero at the beginning

How to Handle:

The algorithm duplicates the zero and shifts all other elements to the right.

Array close to full capacity, with several zeros near the end

How to Handle:

The algorithm handles this correctly, truncating any elements that go beyond the array length.

Array containing negative numbers and zeros

How to Handle:

The algorithm only duplicates zeros and is not affected by negative numbers.

Large array with many zeros scattered throughout

How to Handle:

The in-place modification ensures memory usage is efficient, handling large arrays without significant overhead.

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 range of values for the integers in the input array?
What should happen if the array is empty or null?
Can I assume the array will always have enough space to accommodate the duplicated zeros, or might the duplication truncate the array at the end?
Are we optimizing for space complexity in addition to time complexity?
Could you provide an example input and the corresponding modified output array?

Brute Force Solution

Approach

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

Make a fresh, empty container that is exactly the same size as the original.
Start looking at the first spot in the original container.
Copy whatever you find there into the first empty spot in the new container.
Now, here's the key: If the thing you just copied was a zero, then immediately put another zero in the next empty spot of the new container.
Move to the next thing in the original container and repeat the copying process.
Keep doing this until you've looked at everything in the original container.
If, while adding elements to the new container, you reach the end before you've looked at everything in the original container, then stop filling the new container.
Finally, replace the original container with the contents of this brand new container.

Code Implementation

def duplicate_zeros_brute_force(original_array):
    new_array = [0] * len(original_array)
    new_array_index = 0
    original_array_index = 0

    # Iterate through the original array until we reach the end
    while original_array_index < len(original_array):
        # Copy the element from the original to the new array
        new_array[new_array_index] = original_array[original_array_index]
        new_array_index += 1

        # Check if we've reached the end of the new array
        if new_array_index == len(new_array):
            break

        # If we encounter a zero, duplicate it in the new array
        if original_array[original_array_index] == 0:

            new_array[new_array_index] = 0

            new_array_index += 1

            # Ensure that we are still within the bounds of the new array
            if new_array_index == len(new_array):
                break

        original_array_index += 1

    # Replace the original array with the modified new array
    for index in range(len(original_array)):
        original_array[index] = new_array[index]

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.
Then, determine the final size of the modified list by adding the number of zeros to the original size of the list.
Now, start filling in the modified list by working backwards from the end of the original list.
If you encounter a zero while going backwards, copy it into the modified list, then copy another zero immediately before it. Decrement the counter/position twice to account for the added zero.
If you encounter a number other than zero, just copy it into the modified list. Decrement the counter/position once.
If the modified list size is larger than the original list size, stop copying once you reach the beginning of the original list.

Code Implementation

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

    modified_array_length = len(array) + number_of_zeros

    original_array_length = len(array)

    # Traverse backwards to modify in place.
    current_index = original_array_length - 1
    modified_index = modified_array_length - 1

    while current_index >= 0 and modified_index >= 0:

        if array[current_index] == 0:
            # If we encounter a zero, duplicate it.
            if modified_index < original_array_length:
                array[modified_index] = 0
            modified_index -= 1
            if modified_index < original_array_length:
                array[modified_index] = 0
        else:
            # Copy non-zero elements directly.
            if modified_index < original_array_length:
                array[modified_index] = array[current_index]

        modified_index -= 1
        current_index -= 1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty array	Return immediately without any processing to avoid NullPointerException or other errors.
Array containing only zeros	The algorithm correctly duplicates each zero, shifting the existing zeros to the right.
Array without any zeros	The algorithm does nothing, correctly leaving the array unchanged.
Array with a zero at the end	The algorithm correctly duplicates the zero, shifting the last element off the end.
Array with a zero at the beginning	The algorithm duplicates the zero and shifts all other elements to the right.
Array close to full capacity, with several zeros near the end	The algorithm handles this correctly, truncating any elements that go beyond the array length.
Array containing negative numbers and zeros	The algorithm only duplicates zeros and is not affected by negative numbers.
Large array with many zeros scattered throughout	The in-place modification ensures memory usage is efficient, handling large arrays without significant overhead.

Null or empty array

How to Handle:

Return immediately without any processing to avoid NullPointerException or other errors.

Array containing only zeros

How to Handle:

The algorithm correctly duplicates each zero, shifting the existing zeros to the right.

Array without any zeros

How to Handle:

The algorithm does nothing, correctly leaving the array unchanged.

Array with a zero at the end

How to Handle:

The algorithm correctly duplicates the zero, shifting the last element off the end.

Array with a zero at the beginning

How to Handle:

The algorithm duplicates the zero and shifts all other elements to the right.

Array close to full capacity, with several zeros near the end

How to Handle:

The algorithm handles this correctly, truncating any elements that go beyond the array length.

Array containing negative numbers and zeros

How to Handle:

The algorithm only duplicates zeros and is not affected by negative numbers.

Large array with many zeros scattered throughout

How to Handle:

The in-place modification ensures memory usage is efficient, handling large arrays without significant overhead.