Remove Duplicates from Sorted Array I and II

Two Pointers

Problem

Given an array of sorted numbers, remove all duplicates from it. You should not use any extra space; after removing the duplicates in-place return the length of the subarray that has no duplicate in it.

For example:

Input: [2, 3, 3, 3, 6, 9, 9]
Output: 4
Explanation: The first four elements after 
removing the duplicates will be [2, 3, 6, 9].

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]
Explanation: Your function should return 
length = 5, with the first five elements of 
nums being modified to 0, 1, 2, 3, and 4 
respectively.

Thought Process

• We can use the two pointer approach where one pointer will be used to iterate through the array and the second pointer will be used to keep track of the position of the place where the next non-duplicate number/unique should be placed.

• We will have one pointer for iterating through the array and one pointer for placing the next non-duplcate number.

• We will be moving the non-duplicate numbers to the far left since the array is already sorted

• The index of our nextNonDuplicate pointer is the potential position that can be filled by a non-duplicate number. This spot cannot be equal/the same number of the previous number in the already sorted non-duplicate portion, so we have to compare the previous number to the element of the current index.

Solution

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 1
        j = 1 #non-duplicate index to be filled 
        while i < len(nums):
            if nums[j-1] != nums[i]:
                nums[j] = nums[i]
                j+=1
            i+=1
        return j
                

Follow Up:

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

For example:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3]

Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3]

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i=0
        
        for n in nums:
            if i < 2 or n > nums[i-2]:
                nums[i] = n
                i+=1
        return i
        

Key Points

• Using two pointers: one to iterate through the array and the other pointer to keep track of the position of the next non-duplicate

• The pointer that keeps track of the next non-duplicate position is key for this problem

Time Complexity

• Time: O(N)

• Space: O(1)