Leetcode 1089. Duplicate Zeros
Problem Explanation:
The task is to duplicate elements whenever a 0 is encountered in the array. The corresponding elements to the right will be shifted as a result. We have to do this in place, means we have to manipulate the same array and don't need to create any new array. Elements exceeding the original array are not pushed to the new array.
For example, if we have an array [1,0,2,3,0,4,5,0], after duplicating 0 and shifting elements, the array would look like this: [1,0,0,2,3,0,0,4]. Note that 5 is not included as it exceeds the original length of the array after duplicating zeros.
Approach:
The smart approach will be to first count the number of 0's in the array, which will be used to resize the array. Then we can iterate from the end towards the front of the array and for each non-zero element, we can put it at its appropriate position and for a zero, we will add it two times at its position.
Javascript Solution:
1 2javascript 3var duplicateZeros = function(arr) { 4 let zeros = 0; 5 6 // count number of zeros 7 for(let i=0; i<arr.length; i++){ 8 if(arr[i] === 0) zeros++; 9 } 10 11 // index out of bound issue, limit the length 12 let len = arr.length + zeros; 13 14 // iterate from end and adjust elements 15 for(let i=arr.length-1, j=len; i<j; i--, j--){ 16 17 // if j is within the original length, copy elements 18 if(j<arr.length) 19 arr[j] = arr[i]; 20 21 // if arr[i] is zero, add again it to new position 22 if(arr[i] === 0 && --j < arr.length) 23 arr[j] = arr[i]; 24 } 25};
Python Solution:
1 2python 3class Solution(object): 4 def duplicateZeros(self, arr): 5 zeros = arr.count(0) 6 n = len(arr) 7 for i in range(n-1, -1, -1): 8 if i + zeros < n: 9 arr[i + zeros] = arr[i] 10 if arr[i] == 0: zeros -= 1 11 if i + zeros < n and zeros > -1: 12 arr[i + zeros] = arr[i]
Java Solution:
1 2java 3class Solution { 4 public void duplicateZeros(int[] arr) { 5 int zeros = 0; 6 for(int i = 0; i < arr.length; i++){ 7 if(arr[i] == 0) zeros++; 8 } 9 10 int len = arr.length + zeros; 11 for(int i = arr.length - 1, j = len; i < j; i-- , j--){ 12 13 if(j < arr.length) arr[j] = arr[i]; 14 15 if(arr[i] == 0 && --j < arr.length) arr[j] = arr[i]; 16 } 17 } 18}
C++ Solution:
1
2c++
3class Solution {
4public:
5 void duplicateZeros(vector<int>& arr) {
6 int zeros = count(arr.begin(), arr.end(), 0);
7
8 int len = arr.size() + zeros;
9
10 for (int i = arr.size() - 1, j = len; i < j; i-- , j--) {
11
12 if (j < arr.size()) arr[j] = arr[i];
13
14 if (arr[i] == 0 && --j < arr.size()) arr[j] = arr[i];
15 }
16 }
17};
C# Solution:
1
2csharp
3public class Solution {
4 public void DuplicateZeros(int[] arr) {
5 int zeros = 0;
6 foreach(int num in arr){
7 if(num == 0)
8 zeros++;
9 }
10
11 int len = arr.Length + zeros;
12 for(int i = arr.Length - 1, j = len; i < j; i--, j--){
13 if(j < arr.Length)
14 arr[j] = arr[i];
15 if(arr[i] == 0 && --j < arr.Length)
16 arr[j] = arr[i];
17 }
18 }
19}
Conclusion:
With the help of this efficient approach, we can reduce the time complexity from O(N^2) to O(N) in contrast to the naive solution where we would keep pushing the zeros after encountering it and shifting the elements.Additionally, using the language specific implementation provided here, we are able to make the process more efficient by using the right data structures and algorithms. This approach is not only applicable to just duplicating zeros, it can also be modified and utilized to solve other similar problems.
Nevertheless, the solution is always subject to the requirements and constraints of the problem at hand. Therefore, it's important to understand the problem statement well and then to analyze the data structures and algorithms that can best be used to solve the problem in a language that you are comfortable with.
In conclusion, efficient problem-solving skills combined with a good understanding of different programming languages, can help you to develop an optimized solution in less time. So, keep practicing different types of problems and keep improving your coding skills.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.