-
Notifications
You must be signed in to change notification settings - Fork 0
/
duplicate_zeros.py
64 lines (54 loc) · 2.09 KB
/
duplicate_zeros.py
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
from typing import List
class Solution:
"""
Task:
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.
"""
def duplicateZeros(self, arr: List[int]) -> None:
n = len(arr)
i = 0
while i < n:
if arr[i] == 0:
j = n-1
while j > i:
arr[j] = arr[j-1]
j -= 1
if i+1 < n:
arr[i+1] = 0
i += 1
i += 1
# Method 2 - More efficient
def duplicateZeros(self, arr: List[int]) -> None:
"""
Do not return anything, modify arr in-place instead.
"""
possible_dups = 0
length_ = len(arr) - 1
# Find the number of zeros to be duplicated
for left in range(length_ + 1):
# Stop when left points beyond the last element in the original list
# which would be part of the modified list
if left > length_ - possible_dups:
break
# Count the zeros
if arr[left] == 0:
# Edge case: This zero can't be duplicated. We have no more space,
# as left is pointing to the last element which could be included
if left == length_ - possible_dups:
arr[length_] = 0 # For this zero we just copy it without duplication.
length_ -= 1
break
possible_dups += 1
# Start backwards from the last element which would be part of new list.
last = length_ - possible_dups
# Copy zero twice, and non zero once.
for i in range(last, -1, -1):
if arr[i] == 0:
arr[i + possible_dups] = 0
possible_dups -= 1
arr[i + possible_dups] = 0
else:
arr[i + possible_dups] = arr[i]