Remove Duplicates From Sorted Array

114.Remove Duplicates from Sorted Array

Array

Two Pointers

Problem Statement:

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Return the number of unique elements.

Note: You must do this by modifying the input array in-place with O(1) extra memory.

Algorithm:

1. Use a variable k to track the position of the next unique element.
2. Initialize curr to the first element of the array, as the first element is always unique.
3. Iterate through the array:
   • If the current element is greater than curr, it is unique. Update the array at position k, increment k, and set curr to the current element.
4. Return k, which represents the number of unique elements.

Complexity:

Time: O(n), where n is the length of the array | Space: O(1), as the operation is in-place.

Java Implementation:

public int removeDuplicates(int[] nums) {
    int curr = nums[0];
    int k = 1; // Pointer for the position of unique elements

    for (int num : nums) {
        // If a new unique element is found
        if (num > curr) {
            nums[k++] = num; // Place it in the next unique position
            curr = num; // Update the current unique value
        }
    }

    return k; // The count of unique elements
}
                

Python Implementation:

def removeDuplicates(nums):
    if not nums:
        return 0

    curr = nums[0]
    k = 1  # Pointer for the position of unique elements

    for num in nums:
        # If a new unique element is found
        if num > curr:
            nums[k] = num  # Place it in the next unique position
            k += 1
            curr = num  # Update the current unique value

    return k  # The count of unique elements
                

C++ Implementation:

int removeDuplicates(vector& nums) {
    if (nums.empty()) return 0;

    int curr = nums[0];
    int k = 1; // Pointer for the position of unique elements

    for (int num : nums) {
        // If a new unique element is found
        if (num > curr) {
            nums[k++] = num; // Place it in the next unique position
            curr = num; // Update the current unique value
        }
    }

    return k; // The count of unique elements
}