1089. Duplicate Zeros
Problem Description
The task is to modify a given integer array arr
by duplicating each occurrence of zero within the array. When a zero is duplicated, all elements to the right of that zero need to be shifted to the right as well, and this process must be done without changing the length of the original array. This means that while shifting the elements, any numbers that move beyond the end of the array should not be included in the final array. The modification must be done within the array itself (in-place), without creating a copy of the array or returning a new array.
Intuition
The intuition behind the solution is to first determine the number of zeros which can be duplicated within the bounds of the original array. Not all zeros might be duplicated if there isn't enough space at the end of the array for all the shifts. We start from the beginning of the array and keep track of the position of elements if there were no bounds, counting the space needed for each zero duplication.
Then we iterate from the end of the array backward, copying over each non-zero element or duplicating zeros when needed. If we encounter a situation where duplicating a zero would exceed the actual bounds of the array, we handle that as a special case, making sure we only set the last element to zero and then move backward correctly. This reverse iteration helps in managing the elements already scanned without overwriting them while still duplicating zeros and moving elements to the right.
The solution cleverly uses two pointers and iterates over the array to accomplish the task efficiently without the need for extra space.
Learn more about Two Pointers patterns.
Solution Approach
The provided solution involves a two-pass approach. In the first pass, we calculate the position of the final element and determine how many zeros can be duplicated within the bounds of the array. The second pass is about actually duplicating the zeros and shifting the elements to the right.
First Pass:
- Initialise two pointers
i
andk
. Pointeri
is used to iterate over the elements of the array, andk
is used to keep track of the 'expanded' index as if zeros are being duplicated, but without actually changing the array. - A loop is run until
k
is less than the length of the arrayn
. For non-zero elements, simply increment bothi
andk
by one. For a zero, incrementi
by one andk
by two because duplicating a zero would take an additional space. - After calculating the expanded index, subtract 1 from
i
andk
if the last incrementedk
goes beyond the array bounds (n + 1
), AND the last inspected element was a zero. This is because such a zero cannot be duplicated within the array's bounds. So we retreat one step back to adjust for this scenario.
Second Pass:
- A reverse iteration is done using
i
from where we left off in the first pass, and a new pointerj
which starts at the end of the array (n - 1
). - If the current
arr[i]
is zero, we duplicate it in the positionsarr[j]
andarr[j - 1]
and decrementj
twice since we added two elements. If it's a non-zero, we simply copy it toarr[j]
(arr[j] = arr[i]
) and decrementj
once. - This loop continues (moving
i
andj
backwards) untilj
reaches -1, at which point we've filled the array from the end with duplicated zeros as required.
The key algorithmic idea here is to avoid overwriting elements we have not yet processed, which is why the loop in the second pass iterates backward.
Data structures:
- No additional data structures are used since the operation takes place in-place on the input array
arr
.
Patterns Used:
- Two-pointer technique: One pointer keeps tabs on the position as duplicated, and the other does the array manipulation in reverse to prevent overwriting unprocessed elements.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a simple example to illustrate the solution process using the given approach. Suppose our array, arr
, is [1, 0, 2, 3, 0, 4, 5, 0]
.
First Pass:
- Initialize
i
to 0 andk
to 0. These are our two pointers. - Start iterating over the array
arr
.- First element is
1
(non-zero), so we increment bothi
andk
by one. - Second element is
0
. We incrementi
by one (pointing to2
) andk
by two (since a zero will be duplicated),k
is now pointing to the space where the duplicated0
would be if the array could expand. - Continue this process. By the time we are done,
i
is at the last element (another0
), andk
is pointing beyond the end of the array because this last zero cannot be doubled within the bounds of the array. Sincek
exceeds the array length after duplicating the last zero, we decrement bothi
andk
by one to backtrack.
- First element is
At the end of the first pass, i
is at the second to last element (which is a 5
), and k
indicates the 'expanded' length without the final impossible duplication.
Second Pass:
- Set
j
to the last index ofarr
, which is7
. - Iterate backwards using
i
and shift or duplicate elements.- The element at
i
(which is5
) is copied toarr[j]
. Decrement bothi
andj
. i
now points to the second to last zero, andj
is at the sixth position. We have two5
s atj
andj-1
.- Next,
i
sees a0
. Duplicate it atarr[j]
andarr[j-1]
, putting zero in both places and decrementj
twice. - Continue this process, duplicating zeros and shifting other numbers left.
- When we encounter another 0 (the first
0
in the array), we duplicate it again. - By the time
j
reaches -1, all elements are properly shifted, and zeros are duplicated without overwriting unprocessed elements.
- The element at
After the second pass is complete, arr
should look like [1, 0, 0, 2, 3, 0, 0, 4]
. Non-zero numbers are shifted right, and every zero is duplicated, with excess elements dropped from the end to maintain the original array length.
Solution Implementation
1from typing import List
2
3class Solution:
4 def duplicateZeros(self, arr: List[int]) -> None:
5 """
6 Modify the input array by duplicating each occurrence of zero, shifting the remaining elements to the right.
7 The elements beyond the length of the original array are discarded.
8 """
9 # Find the length of the modified array (including virtual duplicates of zero to the right, that will be eventually discarded)
10 n = len(arr)
11 original_index, extended_index = -1, 0
12 while extended_index < n:
13 original_index += 1
14 # If we encounter a zero, we count it twice for the extended array index
15 extended_index += 2 if arr[original_index] == 0 else 1
16
17 # Start filling the array from the end
18 current_index = n - 1
19 # If the last element in the expanded list is a virtual duplicate of zero, that we need to discard,
20 # set the last position to zero and adjust indexes accordingly
21 if extended_index == n + 1:
22 arr[current_index] = 0
23 original_index -= 1
24 current_index -= 1
25
26 # Iterate backward through the array, filling in the zeros and shifting elements
27 while current_index >= 0:
28 # Replace and shift if the original index points to a zero
29 if arr[original_index] == 0:
30 # Duplicate the zero
31 arr[current_index] = 0
32 current_index -= 1
33 arr[current_index] = 0
34 else:
35 # Copy the current element if it's not a zero
36 arr[current_index] = arr[original_index]
37 # Move to the next elements from the end
38 original_index -= 1
39 current_index -= 1
40
41# Example usage:
42# sol = Solution()
43# arr_example = [1, 0, 2, 3, 0, 4, 5, 0]
44# sol.duplicateZeros(arr_example)
45# The array will be modified to [1, 0, 0, 2, 3, 0, 0, 4] after function call
46
1class Solution {
2
3 // Method to duplicate zeros in the array without using extra space
4 public void duplicateZeros(int[] arr) {
5 int n = arr.length; // n is the length of the array
6 int currentIndex = -1, futureIndex = 0;
7
8 // Find the position from which we cannot shift numbers to the right anymore
9 // without going out of bounds.
10 while (futureIndex < n) {
11 currentIndex++;
12 // If the current element is zero, it will take two positions after duplication; otherwise, it takes one.
13 futureIndex += (arr[currentIndex] == 0) ? 2 : 1;
14 }
15
16 int lastIndex = n - 1; // The last index we can write to in the array
17
18 // If futureIndex goes beyond the array length, set the last element to zero,
19 // as the last zero cannot be duplicated because it does not fit within the array boundary.
20 if (futureIndex == n + 1) {
21 arr[lastIndex--] = 0;
22 currentIndex--; // Skip this zero as it's already been placed in the array
23 }
24
25 // Move through the array from the end and duplicate zeros when necessary.
26 while (lastIndex >= 0) {
27 arr[lastIndex] = arr[currentIndex]; // Copy current element
28
29 // If the current element is zero, we need to duplicate it.
30 if (arr[currentIndex] == 0) {
31 arr[--lastIndex] = arr[currentIndex]; // Set the previous index to zero as well
32 }
33
34 // Move one position back in both, the array and the current index tracker.
35 currentIndex--;
36 lastIndex--;
37 }
38 }
39}
40
1class Solution {
2public:
3 void duplicateZeros(vector<int>& arr) {
4 int n = arr.size(); // Total number of elements in the array.
5 int i = -1; // Initialize i to point to the start of the array.
6 int count = 0; // Initialize count to keep track of the number of elements including duplicates.
7
8 // Calculate the number of elements to consider, including zeros which will be duplicated.
9 while (count < n) {
10 ++i;
11 // If the current element is zero, increment the count by 2, else increment by 1.
12 count += (arr[i] == 0) ? 2 : 1;
13 }
14
15 int j = n - 1; // Initialize j to the last index of the array.
16
17 // If the count is exactly one more than the size, that means the last number to consider is zero
18 // and it will be duplicated to go out of bounds, so we only need to set one zero at the end.
19 if (count == n + 1) {
20 arr[j--] = 0; // Set the last element to zero and decrement j.
21 --i; // Move the i pointer back to avoid considering this zero again.
22 }
23
24 // Iterate backwards through the array and duplicate zeros where necessary.
25 while (j >= 0) {
26 arr[j--] = arr[i]; // Copy the current element.
27 if (arr[i] == 0) {
28 arr[j--] = arr[i]; // Duplicate the zero by setting the previous element to zero as well.
29 }
30 --i; // Move to the next element to consider.
31 }
32 }
33};
34
1// Function to duplicate zeros in an array in-place.
2function duplicateZeros(arr: number[]): void {
3 let n: number = arr.length; // Total number of elements in the array.
4 let i: number = -1; // Initialize 'i' to point to the start of the array.
5 let count: number = 0; // Initialize 'count' to keep track of the number of elements including duplicates.
6
7 // Calculate the number of elements to consider, including zeros which will be duplicated.
8 while (count < n) {
9 i++;
10 count += arr[i] === 0 ? 2 : 1; // If the current element is zero, increment 'count' by 2, else by 1.
11 }
12
13 let j: number = n - 1; // Initialize 'j' to the last index of the array.
14
15 // If 'count' is exactly one more than the size, the last number to consider is zero
16 // and it will be duplicated to go out of bounds. Set one zero at the end.
17 if (count === n + 1) {
18 arr[j] = 0; // Set the last element to zero.
19 j--; // Decrement 'j'.
20 i--; // Move the 'i' pointer back to avoid considering this zero again.
21 }
22
23 // Iterate backwards through the array and duplicate zeros where necessary.
24 while (j >= 0) {
25 arr[j] = arr[i]; // Copy the current element.
26 j--; // Decrement 'j'.
27 if (arr[i] === 0 && j >= 0) {
28 arr[j] = 0; // Duplicate the zero by setting the previous element to zero as well.
29 j--; // Decrement 'j' after duplication.
30 }
31 i--; // Move to the next element to consider.
32 }
33}
34
35// Example usage:
36// let arrExample = [1, 0, 2, 3, 0, 4, 5, 0];
37// duplicateZeros(arrExample);
38// console.log(arrExample); // Output would be [1, 0, 0, 2, 3, 0, 0, 4]
39
Time and Space Complexity
The given code modifies the input array arr
in-place to duplicate each occurrence of zero, shifting the remaining elements to the right. Here's the complexity analysis:
- Time Complexity:
The time complexity of the code is O(n)
. It consists of two pass-through procedures over the array: the first pass counts the zeros (in a way that accounts for the shift that will happen once zeros are duplicated), and the second pass actually duplicates the zeros from the end to the beginning. Each pass runs in linear time relative to the number of elements in the array (n
).
Assuming n
is the length of arr
, the first loop runs until k
, which is the expanded size taking into account the duplicated zeros, is greater than or equal to n
. Each iteration potentially advances i
by 1 and k
by either 1 (non-zero) or 2 (zero), meaning it will never iterate more than n
times (because k
starts from zero and increases to at least n
).
The second loop runs while j
, which starts at n - 1
and decreases, is non-negative. On each iteration, it potentially copies a value from i
to j
and decreases j
by 1 (or 2 if the value is 0 and it's not the case where k == n + 1
). Again, this loop will never execute more than n
times.
- Space Complexity:
The space complexity of the code is O(1)
. The algorithm modifies the array in place and uses a constant amount of extra space for variables i
, j
, and k
. Regardless of the size of the input array, the space used by these variables does not change, so the space complexity is constant.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
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