Remove Duplicates From Sorted Array

Problem Description

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. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

1. Modify the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially.
2. Return k.

Examples

Constraints

• 1 <= nums.length <= 3 * 10⁴
• -100 <= nums[i] <= 100
• nums is sorted in non-decreasing order.

Write Pointer for Unique Elements

Since the array is already sorted, all duplicates are adjacent. We can maintain a write pointer k initialized to 1 (the first element is always unique). We iterate through the array starting from index 1 with a read pointer i. If nums[i] is not equal to nums[i - 1] (indicating a new unique value), copy nums[i] to nums[k] and increment k. This updates the unique values at the front of the array in a single linear pass.

Solution 1: Fast and Slow Two Pointers

Maintain a slow write pointer to overwrite duplicate values.

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int k = 1; // write pointer for unique elements
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[k] = nums[i];
                k++;
            }
        }
        return k;
    }
}

class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        if not nums:
            return 0
        k = 1  # write pointer for unique elements
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                nums[k] = nums[i]
                k += 1
        return k

#include <vector>

class Solution {
public:
    int removeDuplicates(std::vector<int>& nums) {
        if (nums.empty()) return 0;
        int k = 1; // write pointer for unique elements
        for (size_t i = 1; i < nums.size(); i++) {
            if (nums[i] != nums[i - 1]) {
                nums[k] = nums[i];
                k++;
            }
        }
        return k;
    }
};

Complexity Analysis

• Time Complexity: O(n) since we scan the array elements once.
• Space Complexity: O(1) auxiliary space as we modify the array in-place.

Where It Breaks

If the input array is unsorted, duplicate elements are not adjacent, and this approach will fail. Under those conditions, you must sort the array first (which increases time complexity to O(n log n)) or use a hash set (which increases space complexity to O(n)).

Common Mistakes

• Incorrect loop start index: Starting the loop at index 0 instead of 1, which causes an index out of bounds error when checking nums[i - 1].
• Double pointer increments: Incrementing both pointers in all branches, which fails to skip over consecutive duplicates.

Frequently Asked Questions

Can we solve this using a hash set? Yes. You can filter duplicates using a set and write them back to the array. However, this uses O(n) auxiliary space, violating the O(1) space constraint of the problem.

What does the returned integer k represent? It represents the total count of unique elements, which is also the exact length of the prefix containing the sorted unique elements.

← All Problems