26. Remove Duplicates From Sorted Array - Explanation

Description

You are given an integer array nums sorted in non-decreasing order. Your task is to remove duplicates from nums in-place so that each element appears only once.

After removing the duplicates, return the number of unique elements, denoted as k, such that the first k elements of nums contain the unique elements.

Note:

The order of the unique elements should remain the same as in the original array.
It is not necessary to consider elements beyond the first k positions of the array.
To be accepted, the first k elements of nums must contain all the unique elements.

Return k as the final result.

Example 1:

Input: nums = [1,1,2,3,4]

Output: [1,2,3,4]

Explanation: You should return k = 4 as we have four unique elements.

Example 2:

Input: nums = [2,10,10,30,30,30]

Output: [2,10,30]

Explanation: You should return k = 3 as we have three unique elements.

Constraints:

1 <= nums.length <= 30,000
-100 <= nums[i] <= 100
nums is sorted in non-decreasing order.

Topics

Array Two Pointers

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Two Pointers - Using a read pointer and write pointer to modify arrays in-place
In-Place Array Modification - Overwriting elements without using extra space
Sorted Array Properties - Understanding that duplicates are always adjacent in sorted arrays

1. Sorted Set

Intuition

A set automatically removes duplicates, and a sorted set maintains order. We insert all elements into a sorted set, then copy the unique elements back to the original array. This approach is simple but uses extra space and doesn't take advantage of the array already being sorted.

Algorithm

Insert all elements from the array into a sorted set to eliminate duplicates.
Copy the unique elements from the set back into the beginning of the original array.
Return the size of the set (number of unique elements).

Note: This approach is simple but uses extra O(n) space.

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        unique = sorted(set(nums))
        nums[:len(unique)] = unique
        return len(unique)

public class Solution {
    public int removeDuplicates(int[] nums) {
        TreeSet<Integer> unique = new TreeSet<>();
        for (int num : nums) {
            unique.add(num);
        }
        int i = 0;
        for (int num : unique) {
            nums[i++] = num;
        }
        return unique.size();
    }
}

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        set<int> unique(nums.begin(), nums.end());
        int i = 0;
        for (int num : unique) {
            nums[i++] = num;
        }
        return unique.size();
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    removeDuplicates(nums) {
        const unique = Array.from(new Set(nums)).sort((a, b) => a - b);
        for (let i = 0; i < unique.length; i++) {
            nums[i] = unique[i];
        }
        return unique.length;
    }
}

public class Solution {
    public int RemoveDuplicates(int[] nums) {
        int[] unique = nums.Distinct().OrderBy(x => x).ToArray();
        Array.Copy(unique, nums, unique.Length);
        return unique.Length;
    }
}

func removeDuplicates(nums []int) int {
    seen := make(map[int]bool)
    var unique []int
    for _, num := range nums {
        if !seen[num] {
            seen[num] = true
            unique = append(unique, num)
        }
    }
    sort.Ints(unique)
    copy(nums, unique)
    return len(unique)
}

class Solution {
    fun removeDuplicates(nums: IntArray): Int {
        val unique = nums.toSet().sorted()
        for (i in unique.indices) {
            nums[i] = unique[i]
        }
        return unique.size
    }
}

class Solution {
    func removeDuplicates(_ nums: inout [Int]) -> Int {
        let unique = Array(Set(nums)).sorted()
        for i in 0..<unique.count {
            nums[i] = unique[i]
        }
        return unique.count
    }
}

impl Solution {
    pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
        let unique: BTreeSet<i32> = nums.iter().cloned().collect();
        let mut i = 0;
        for &num in &unique {
            nums[i] = num;
            i += 1;
        }
        unique.len() as i32
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

2. Two Pointers - I

Intuition

Since the array is sorted, duplicates are adjacent. We use two pointers: one (l) marks where to place the next unique element, and another (r) scans through the array. When r finds a new value (different from what's at l), we copy it to position l and advance both pointers. This modifies the array in-place.

Algorithm

Initialize both pointers l and r to 0.
Copy the current element at r to position l.
Skip all duplicates by advancing r while consecutive elements are equal.
Move l forward to prepare for the next unique element.
Return l as the count of unique elements.

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        n = len(nums)
        l = r = 0
        while r < n:
            nums[l] = nums[r]
            while r < n and nums[r] == nums[l]:
                r += 1
            l += 1
        return l

public class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length, l = 0, r = 0;
        while (r < n) {
            nums[l] = nums[r];
            while (r < n && nums[r] == nums[l]) {
                r++;
            }
            l++;
        }
        return l;
    }
}

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size(), l = 0, r = 0;
        while (r < n) {
            nums[l] = nums[r];
            while (r < n && nums[r] == nums[l]) {
                r++;
            }
            l++;
        }
        return l;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    removeDuplicates(nums) {
        let n = nums.length,
            l = 0,
            r = 0;
        while (r < n) {
            nums[l] = nums[r];
            while (r < n && nums[r] === nums[l]) {
                r++;
            }
            l++;
        }
        return l;
    }
}

public class Solution {
    public int RemoveDuplicates(int[] nums) {
        int n = nums.Length;
        int l = 0, r = 0;

        while (r < n) {
            nums[l] = nums[r];
            while (r < n && nums[r] == nums[l]) {
                r++;
            }
            l++;
        }

        return l;
    }
}

func removeDuplicates(nums []int) int {
    n := len(nums)
    l, r := 0, 0
    for r < n {
        nums[l] = nums[r]
        for r < n && nums[r] == nums[l] {
            r++
        }
        l++
    }
    return l
}

class Solution {
    fun removeDuplicates(nums: IntArray): Int {
        val n = nums.size
        var l = 0
        var r = 0
        while (r < n) {
            nums[l] = nums[r]
            while (r < n && nums[r] == nums[l]) {
                r++
            }
            l++
        }
        return l
    }
}

class Solution {
    func removeDuplicates(_ nums: inout [Int]) -> Int {
        let n = nums.count
        var l = 0, r = 0
        while r < n {
            nums[l] = nums[r]
            while r < n && nums[r] == nums[l] {
                r += 1
            }
            l += 1
        }
        return l
    }
}

impl Solution {
    pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
        let n = nums.len();
        let mut l = 0;
        let mut r = 0;
        while r < n {
            nums[l] = nums[r];
            while r < n && nums[r] == nums[l] {
                r += 1;
            }
            l += 1;
        }
        l as i32
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

3. Two Pointers - II

Intuition

A more elegant approach: we compare each element with its predecessor. Since duplicates are consecutive in a sorted array, an element is unique if it differs from the one before it. We maintain a write pointer that only advances when we find a new unique value.

Algorithm

Start with l = 1 since the first element is always unique.
Iterate r from 1 to the end of the array.
If nums[r] differs from nums[r - 1], it's a new unique value.
Copy it to position l and increment l.
Return l as the count of unique elements.

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        l = 1
        for r in range(1, len(nums)):
            if nums[r] != nums[r - 1]:
                nums[l] = nums[r]
                l += 1
        return l

public class Solution {
    public int removeDuplicates(int[] nums) {
        int l = 1;
        for (int r = 1; r < nums.length; r++) {
            if (nums[r] != nums[r - 1]) {
                nums[l++] = nums[r];
            }
        }
        return l;
    }
}

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int l = 1;
        for (int r = 1; r < nums.size(); r++) {
            if (nums[r] != nums[r - 1]) {
                nums[l++] = nums[r];
            }
        }
        return l;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    removeDuplicates(nums) {
        let l = 1;
        for (let r = 1; r < nums.length; r++) {
            if (nums[r] !== nums[r - 1]) {
                nums[l++] = nums[r];
            }
        }
        return l;
    }
}

public class Solution {
    public int RemoveDuplicates(int[] nums) {
        int l = 1;
        for (int r = 1; r < nums.Length; r++) {
            if (nums[r] != nums[r - 1]) {
                nums[l] = nums[r];
                l++;
            }
        }

        return l;
    }
}

class Solution {
    fun removeDuplicates(nums: IntArray): Int {
        var l = 1
        for (r in 1 until nums.size) {
            if (nums[r] != nums[r - 1]) {
                nums[l++] = nums[r]
            }
        }
        return l
    }
}

class Solution {
    func removeDuplicates(_ nums: inout [Int]) -> Int {
        var l = 1
        for r in 1..<nums.count {
            if nums[r] != nums[r - 1] {
                nums[l] = nums[r]
                l += 1
            }
        }
        return l
    }
}

impl Solution {
    pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
        let mut l = 1;
        for r in 1..nums.len() {
            if nums[r] != nums[r - 1] {
                nums[l] = nums[r];
                l += 1;
            }
        }
        l as i32
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Not Leveraging the Sorted Property

The array is already sorted, meaning duplicates are always adjacent. Some solutions use a hash set or sort the array again, which wastes time and space. Since duplicates are consecutive, you only need to compare each element with its predecessor (or the last written element) to detect duplicates in O(1) space.

Returning the Wrong Value

The function should return the count of unique elements, not modify and return the array itself. Additionally, the returned length k means the first k elements of nums contain the unique values. Some solutions off-by-one error by returning l - 1 instead of l, or forget that the write pointer already represents the count of unique elements written.