""" 0026.1 - Remove Duplicates from Sorted Array - Solution 1 - Brute Force (Using a Set) """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def removeDuplicates(self, nums: List[int]) -> int:
"""Remove Duplicates Function"""
seen = set()
unique = []
for num in nums:
if num not in seen:
seen.add(num)
unique.append(num)
for i in range(len(unique)):
nums[i] = unique[i]
return len(unique)
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
nums1 = [1, 1, 2]
k1 = Solution().removeDuplicates(nums1)
print(k1, nums1[:k1]) # 2 [1, 2]
nums2 = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
k2 = Solution().removeDuplicates(nums2)
print(k2, nums2[:k2]) # 5 [0, 1, 2, 3, 4]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0026.2 - Remove Duplicates from Sorted Array - Solution 2 - Two Pointer (Optimal) """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def removeDuplicates(self, nums: List[int]) -> int:
"""Remove Duplicates Function"""
if not nums:
return 0
i = 0 # slow pointer — last unique element position
for j in range(1, len(nums)):
if nums[j] != nums[i]:
i += 1
nums[i] = nums[j]
return i + 1
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
nums1 = [1, 1, 2]
k1 = Solution().removeDuplicates(nums1)
print(k1, nums1[:k1]) # 2 [1, 2]
nums2 = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
k2 = Solution().removeDuplicates(nums2)
print(k2, nums2[:k2]) # 5 [0, 1, 2, 3, 4]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()