Leetcode 26. Remove Duplicates from Sorted Array

Problem

Leetcode 26 - Remove Duplicates from Sorted Array

Example:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

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 k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Approach

Since this array is already sorted, we can have 2 pointer k where it starts at 0 and r where it starts from 1.

• If nums[k] == nums[r], since they’re repeating we can ignore it and increment r
• If nums[k] != nums[r], since we are seeing a different element, we increment k then swap with nums[r], because upto element k array doesn’t have any repeating number.

Finally we return k+1, since we’ve been counting k starting at 0. The size should be k+1

Visualization of the Approach:

nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
        k  r

Since nums[k] == nums[r] continue

nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
        k     r
Since nums[k] != nums[r] increment k, then swap elements

nums = [0, 1, 0, 1, 1, 2, 2, 3, 3, 4]
           k     r
Since nums[k] == nums[r] continue

nums = [0, 1, 0, 1, 1, 2, 2, 3, 3, 4]
           k        r
Since nums[k] == nums[r] continue

nums = [0, 1, 0, 1, 1, 2, 2, 3, 3, 4]
           k           r
Since nums[k] != nums[r] increment k, then swap elements

nums = [0, 1, 2, 1, 1, 0, 2, 3, 3, 4]
              k           r
Since nums[k] == nums[r] continue

nums = [0, 1, 2, 1, 1, 0, 2, 3, 3, 4]
              k              r
Since nums[k] != nums[r] increment k, then swap elements

nums = [0, 1, 2, 3, 1, 0, 2, 1, 3, 4]
                 k              r
Since nums[k] == nums[r] continue

nums = [0, 1, 2, 3, 1, 0, 2, 1, 3, 4]
                 k                 r
Since nums[k] != nums[r] increment k, then swap elements

nums = [0, 1, 2, 3, 4, 0, 2, 1, 3, 1]
                    k              

We return k+1 since k represents the index which starts from 0

Here is the Python code for the solution:

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        k = 0 
        for r in range(1, len(nums)):
            if nums[k] == nums[r]:
                continue
        
            k += 1
            nums[k] = nums[r]
        
        return k+1         
    

Time Complexity and Space Complexity

Time Complexity: $O(n + m)$ where $m$ is length of nums1 $n$ is length of nums2

Space Complexity: $O(1)$