26. Remove Duplicates from Sorted Array

Intuition

Given a sorted array, the task is to remove duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. This can be efficiently done by leveraging the fact that the array is already sorted, which allows us to use a two-pointer technique to identify and overwrite duplicates.

Approach

1. If the array is empty, return 0.
2. Initialize a variable k to 0. This will keep track of the position in the array where the next unique element should be placed.
3. Iterate through the array starting from the second element.
4. For each element, compare it with the element at position k. If they are different, increment k and update the element at position k with the current element.
5. After the loop, k + 1 will be the number of unique elements in the array.
6. Return k + 1.

Complexity

The time complexity is O(n), where n is the length of the array. This is because we iterate through the array once.

Code

C++

class Solution {
public:
    int removeDuplicates(vector& nums) {
        int n = nums.size();
        if (n == 0) return 0;

        int k = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[k]) {
                nums[++k] = nums[i];
            }
        }
        return k + 1;
    }
};

Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0

        k = 0
        for i in range(1, n):
            if nums[i] > nums[k]:
                k += 1
                nums[k] = nums[i]

        return k + 1

Java

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;

        int k = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[k]) {
                nums[++k] = nums[i];
            }
        }
        return k + 1;
    }
}

JavaScript

var removeDuplicates = function(ar) {
    let n = ar.length;
    let i = 0, k = 0;

    for(let i = 0; i < n; i++) 
        if(ar[i] > ar[k])
            ar[++k] = ar[i];
    
    return k+1;
};