Solution to LeetCode 26 Remove Duplicates from Sorted Array, LeetCode 27 Remove Element, LeetCode 283 Move zeros, and LeetCode 977 Squares of a Sorted Array.
LeetCode 26
Remove Duplicates from Sorted Array (Easy) [link]
1] Brute Force Solution. (ETL) Time complexity O(n^2). Space complexity O(1).
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
n = len(nums)
count = 0
i = 1
while i< n-count:
if nums[i-1] == nums[i]:
for j in range(i+1, n):
nums[j-1] = nums[j]
count += 1
else:
i += 1
return n-count
2] Double Pointers.
Since the input array is sorted, the order matters. We can’t directly switch the value in the front with the value at the end. So both pointers start from the beginning. The faster pointer is moving to find different number. The slow pointer is moving to accept new different number, and always be in the final position of the result array. The while loop stops when the faster pointer is out of the array.
Time complexity O(n). Space complexity O(1).
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
n = len(nums)
if n <= 1: return n
fast = slow = 1
while fast < n:
if nums[fast] != nums[fast-1]:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
LeetCode 27
Remove Element (Easy) [link]
1] Brute Force Solution: iterate through the array if val is found, move the val to the end. count records the occurrence of val in nums. The point i is used to move val to the end. It moves to the next index only when it points to a non-val value. Time complexity is O(n^2). Space complexity O(1).
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
n=len(nums)
count=0
i=0
while (i<n-count):
if nums[i]==val:
for j in range(i+1,n):
nums[j-1]=nums[j]
count+=1
else:
i+=1
return n-count
2] Double Pointers.
Time complexity O(n). Space complexity O(1).
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
n = len(nums)
l = 0
r = n-1
while l <= r:
if nums[l] == val: # is val
nums[l], nums[r]= nums[r], nums[l] # switch
r-=1
else: # not val
l+=1
# print(nums)
return l
LeetCode 283
Move zeros. (Easy) [link]
1] Brute Force Solution. Use count to track the number of zeros, so i won’t access twice those previous zeros. Time complexity O(n^2). Space complexity O(1).
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
i = 0
count = 0 # avoid endless loop
while i<n-count:
if nums[i] == 0:
for j in range(i+1, n):
nums[j-1], nums[j] = nums[j], nums[j-1]
count+=1
else:
i+=1
return nums
2] Double Pointers. The fast pointer finds the next non-zero value and switch with the value pointed by the slow pointer, making sure the slow pointer always points to the non-zero value. Time complexity O(n). Space complexity O(1).
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
fast = slow = 0
while fast<n:
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
fast+=1
return nums
LeetCode 977
Squares of a Sorted Array (Easy) [link]
1] Brute Force Solution. Square all numbers and sort the list. Time complexity O(n + n Log n). Space complexity O(n).
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
res=[]
for num in nums:
res.append(num**2)
return sorted(res)
2] Double Pointers. Starting from the middle, because the numbers in the middle are smaller.
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
# if size is 1
if len(nums) == 1:
return [nums[0]*nums[0]]
# if all negative
if nums[-1] < 0:
i = len(nums)
j = i-1
else:
# if not all negative or all positive
i = 0
while nums[i] < 0:
i += 1
j = i-1
res = []
while j >= 0 and i <= len(nums)-1:
if nums[j]*nums[j] > nums[i]*nums[i]:
res.append(nums[i]*nums[i])
i += 1
else:
res.append(nums[j]*nums[j])
j -= 1
while j >= 0:
res.append(nums[j]*nums[j])
j -= 1
while i <= len(nums)-1:
res.append(nums[i]*nums[i])
i += 1
return res
3] Double Pointers. Starting from the ends and reverse, or starting from the ends and add to the result list from the end.
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
i = 0
j = len(nums)-1
res = []
while i<=j:
l2 = nums[i]**2
r2 = nums[j]**2
if l2 < r2:
res.append(r2)
j -= 1
else:
res.append(l2)
i += 1
return res[::-1]
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
i = 0
j = len(nums)-1
k = len(nums)-1
res = [-1] * len(nums)
while i<=j:
l2 = nums[i]**2
r2 = nums[j]**2
if l2 < r2:
res[k] = r2
j -= 1
else:
res[k] = l2
i += 1
k -= 1
return res
