0026 - Remove Duplicates from Sorted Array

Difficulty

Easy

Language

Python

URL

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

Solution 1 - Brute Force (Using a Set)

Create a new list by iterating through the array and only adding elements that haven't been seen before (tracked via a set). Then copy the unique elements back into the original array and return the count.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 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()

Solution 2 - Two Pointer (Optimal)

Use two pointers: a slow pointer i that tracks the position of the last unique element, and a fast pointer j that scans through the array. When nums[j] differs from nums[i], increment i and overwrite nums[i] with nums[j]. Since the array is sorted, all duplicates are adjacent, so this single pass is sufficient.

TimeComplexity: O(n)

SpaceComplexity: O(1)

""" 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()