26. Remove Duplicates from Sorted Array

Problem Description

Given a sorted integer array nums, remove duplicates in-place such that each unique element appears only once. The relative order of the elements should be maintained. Return the number of unique elements. The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

Solution: Single Pass

This problem can be efficiently solved using a two-pointer approach in a single pass. We'll use one pointer (k) to track the index of the next unique element and another implicit pointer to iterate through the array.

Algorithm:

1. Initialize k to 0. This represents the index where the next unique element will be placed.
2. Iterate through the nums array.
3. For each element x:
   • If k is 0 (meaning it's the first element) or x is different from nums[k-1] (the last unique element added), then it's a unique element.
   • Place x at nums[k].
   • Increment k.
4. After iterating through all elements, k will hold the number of unique elements, and the first k elements of nums will contain these unique elements.
5. Return k.

Time Complexity: O(n), where n is the length of the array. We iterate through the array once.

Space Complexity: O(1). We use only a constant amount of extra space.

Code Implementation

The code implementations in various programming languages are as follows:

Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        k = 0
        for x in nums:
            if k == 0 or x != nums[k - 1]:
                nums[k] = x
                k += 1
        return k

Java

class Solution {
    public int removeDuplicates(int[] nums) {
        int k = 0;
        for (int x : nums) {
            if (k == 0 || x != nums[k - 1]) {
                nums[k++] = x;
            }
        }
        return k;
    }
}

C++

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k = 0;
        for (int x : nums) {
            if (k == 0 || x != nums[k - 1]) {
                nums[k++] = x;
            }
        }
        return k;
    }
};

JavaScript

var removeDuplicates = function(nums) {
    let k = 0;
    for (let x of nums) {
        if (k === 0 || x !== nums[k - 1]) {
            nums[k++] = x;
        }
    }
    return k;
};

Go

func removeDuplicates(nums []int) int {
    k := 0
    for _, x := range nums {
        if k == 0 || x != nums[k-1] {
            nums[k] = x
            k++
        }
    }
    return k
}

TypeScript

function removeDuplicates(nums: number[]): number {
    let k: number = 0;
    for (const x of nums) {
        if (k === 0 || x !== nums[k - 1]) {
            nums[k++] = x;
        }
    }
    return k;
}

All these implementations follow the same single-pass algorithm, achieving linear time and constant space complexity. The differences are primarily in syntax and language-specific features.