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 <= 1040 <= arr[i] <= 9The two-pointer technique allows us to shift elements efficiently. We use two pointers, one for the original array and one for the new modified version. The first pointer, 'i', traverses the array to count the potential size if zeros were duplicated (up to the length of the array). The second pointer, 'j', keeps track of the position for the final result.
We use these pointers to replicate zeros and copy other elements backward from the end.
The solution uses a two-pass method. The first pass counts the number of zeros and calculates the new length by incorporating the duplicating zeros, without exceeding the original array's bounds. The second pass migrates elements from the end to start, duplicating zeros when they appear.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n). We go through the array twice, so it's linear with respect to the number of elements.
Space Complexity: O(1). Apart from input, we use a constant amount of extra space.
This approach processes the array by creating temporary space for duplicated zeros and then shifting elements accordingly. It uses a separate count to track effective elements and carefully adjusts them in-memory to avoid exceeding the bounds.
This C solution simulates the shifting of elements in place by inserting extra zero wherever required. It temporarily shifts each element to make space for duplication effectively.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2). In the worst case, each zero causes a shift of the remaining array.
Space Complexity: O(1). No extra space is used aside from input.
| Approach | Complexity |
|---|---|
| Approach 1: Two-Pointer Method | Time Complexity: O(n). We go through the array twice, so it's linear with respect to the number of elements. |
| Approach 2: Simulate In-Place Shift | Time Complexity: O(n^2). In the worst case, each zero causes a shift of the remaining array. |
Move Zeroes - Leetcode 283 - Python • NeetCode • 100,922 views views
Watch 9 more video solutions →Practice Duplicate Zeros with our built-in code editor and test cases.
Practice on FleetCode