Remove Duplicates from Sorted Array

Problem Summary

• Given a sorted array with duplicates, put all non-duplicates in the sorted order at the start and put all duplicates at the end
• Return the length of non-duplicate array
• Do everything in place

Key Observations

• Have to solve in $O(1)$ space

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Two Pointers

Time & Space Complexity

• Time: $O(n)$ → Reason: Iterating through each element once
• Space: $O(1)$ → Reason: Not copying the array

Code

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        l = 1

        for r in range(1, len(nums)):
            if nums[r] != nums[l - 1]:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
        return l

Common Mistakes / Things I Got Stuck On

• I could not figure out the if statement
• Was over complicating pointer movement

YouTube Solution