Hex.*

LC1089 - Duplicate Zeros

Posted on In
Leetcode: 133/2658 (56+63+14)

Description

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 <= 104
0 <= arr[i] <= 9

Solution

Simulation

  • A combination of python’s built-in functions pop and insert is used.

  • The time complexity of insert is O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Lists:
                               Complexity
Operation     | Example      | Class         | Notes
--------------+--------------+---------------+-------------------------------
Index         | l[i]         | O(1)          |
Store         | l[i] = 0     | O(1)          |
Length        | len(l)       | O(1)          |
Append        | l.append(5)  | O(1)          |
Clear         | l.clear()    | O(1)          | similar to l = []

Slice         | l[a:b]       | O(b-a)        | l[1:5]:O(l)/l[:]:O(len(l)-0)=O(N)
Extend        | l.extend(...)| O(len(...))   | depends only on len of extension
Construction  | list(...)    | len(...)      | depends on lenghth of argument

check ==, !=  | l1 == l2     | O(N)          |
Insert        | l[a:b] = ... | O(N)          |
Delete        | del l[i]     | O(N)          |
Remove        | l.remove(...)| O(N)          |
Containment   | x in/not in l| O(N)          | searches list
Copy          | l.copy()     | O(N)          | Same as l[:] which is O(N)
Pop           | l.pop(...)   | O(N)          |
Pop           | l.pop()      | O(1)          | same as l.pop(-1), popping at end
Extreme value | min(l)/max(l)| O(N)          |
Reverse       | l.reverse()  | O(N)          |
Iteration     | for v in l:  | O(N)          |

Sort          | l.sort()     | O(N Log N)    | key/reverse doesn't change this
Multiply      | k*l          | O(k N)        | 5*l is O(N): len(l)*l is O(N**2)
1
2
3
4
5
6
7
8
9
10
11
12
13
# O(n^2) time | O(1) space
class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        idx = 0
        while idx < len(arr):
            if arr[idx] == 0:
                arr.pop()
                arr.insert(idx, 0)
                idx+=1
            idx+=1

Two Pointers

Traverse the number of zeros and the end position of the data,
Imagine that each zero is pushed onto the stack twice, and the traversal ends when the stack is as long as the array. Pops elements from the top of the stack in order.

A pointer left represents the data position (the top of the stack), and a pointer represents the write position (the current write position of the original array)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# O(n) time | O(1) space
class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        left = -1
        top_idx = 0
        
        while top_idx < len(arr):
            left+=1
            if arr[left]:
                top_idx+=1
            else:
                top_idx+=2
            
        right = len(arr)-1
        if top_idx == len(arr) +1:
            arr[right] = 0
            right -=1
            left -=1
        
        while right >=0:
            arr[right] = arr[left]
            right -=1
            if arr[left] == 0:
                arr[right] = arr[left]
                right -=1
            left-=1