Skip to main content
CodePeetCodePeet
CodePeet 250

Remove Duplicates from Sorted Array

EASYProblemSolveExternal Links

Description

Given an integer array nums sorted in non-decreasing order, remove the duplicate elements in-place so that each unique element appears only once. The relative order of the elements must remain the same.

After removing duplicates, let k be the number of unique elements. The first k positions of nums should contain these unique elements in their original sorted order. What you leave beyond index k - 1 does not matter.

Return the value k — the count of unique elements.

Note: You must modify the array in-place with O(1) extra memory. The judge verifies that the first k elements of nums match the expected unique values.

Examples

Example 1

Input: nums = [1, 1, 2]

Output: 2, nums = [1, 2, _]

Explanation: There are two unique elements: 1 and 2. After removing duplicates, the first two positions of nums hold [1, 2]. The underscore represents a position whose value does not matter. We return k = 2.

Example 2

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

Output: 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]

Explanation: There are five unique elements: 0, 1, 2, 3, and 4. After removing duplicates, the first five positions of nums hold [0, 1, 2, 3, 4]. The remaining positions are irrelevant. We return k = 5.

Example 3

Input: nums = [1, 2, 3]

Output: 3, nums = [1, 2, 3]

Explanation: All elements are already unique. No duplicates to remove. We return k = 3 and the array is unchanged.

Constraints

  • 1 ≤ nums.length ≤ 3 × 10^4
  • -100 ≤ nums[i] ≤ 100
  • nums is sorted in non-decreasing order

Editorial

Brute Force

Intuition

The most straightforward way to remove duplicates is to use an extra data structure to collect unique elements, then write them back into the original array.

Since the array is sorted, duplicate values are always adjacent. We can scan through the array and whenever we encounter a value different from the last one we recorded, we know it is a new unique element. We store each unique element into a temporary list, and after scanning, we copy the unique elements back into the beginning of nums.

Think of it like reading through a stack of alphabetically sorted name cards. You go through them one by one, and every time you see a name you have not seen before, you write it down on a fresh piece of paper. At the end, your piece of paper has all the unique names in order.

Step-by-Step Explanation

Let's trace through with nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]:

Step 1: Create an empty list called unique. Add the first element nums[0] = 0 to it. unique = [0].

Step 2: Check nums[1] = 0. Same as the last unique element (0). Skip it.

Step 3: Check nums[2] = 1. Different from the last unique element (0). Add 1. unique = [0, 1].

Step 4: Check nums[3] = 1. Same as 1. Skip.

Step 5: Check nums[4] = 1. Same as 1. Skip.

Step 6: Check nums[5] = 2. Different from 1. Add 2. unique = [0, 1, 2].

Step 7: Check nums[6] = 2. Same as 2. Skip.

Step 8: Check nums[7] = 3. Different from 2. Add 3. unique = [0, 1, 2, 3].

Step 9: Check nums[8] = 3. Same as 3. Skip.

Step 10: Check nums[9] = 4. Different from 3. Add 4. unique = [0, 1, 2, 3, 4].

Step 11: Copy unique list back into nums. nums = [0, 1, 2, 3, 4, ...]. Return k = 5.

Brute Force — Collect Uniques into Extra List — Watch how we scan through the sorted array, picking up each new unique element into a separate list, then copy the result back.

Algorithm

  1. Create an empty list unique
  2. Add nums[0] to unique (the first element is always unique)
  3. For each subsequent element nums[i] (i from 1 to n-1):
    • If nums[i] differs from the last element in unique, add it to unique
    • Otherwise, skip it (it is a duplicate)
  4. Copy all elements from unique back into the beginning of nums
  5. Return the size of unique as k

Code

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        vector<int> unique;
        unique.push_back(nums[0]);
        
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] != unique.back()) {
                unique.push_back(nums[i]);
            }
        }
        
        for (int i = 0; i < unique.size(); i++) {
            nums[i] = unique[i];
        }
        
        return unique.size();
    }
};
class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        unique = [nums[0]]
        
        for i in range(1, len(nums)):
            if nums[i] != unique[-1]:
                unique.append(nums[i])
        
        for i in range(len(unique)):
            nums[i] = unique[i]
        
        return len(unique)
class Solution {
    public int removeDuplicates(int[] nums) {
        List<Integer> unique = new ArrayList<>();
        unique.add(nums[0]);
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != unique.get(unique.size() - 1)) {
                unique.add(nums[i]);
            }
        }
        
        for (int i = 0; i < unique.size(); i++) {
            nums[i] = unique.get(i);
        }
        
        return unique.size();
    }
}

Complexity Analysis

Time Complexity: O(n)

We scan through the array once to collect unique elements (O(n)), then copy them back (O(k) where k ≤ n). Total: O(n).

Space Complexity: O(n)

In the worst case (all elements unique), the temporary list stores all n elements. This is the main drawback — we use O(n) extra space, but the problem asks us to do it with O(1) extra memory.

Why This Approach Is Not Efficient

While the brute force runs in O(n) time (which is already optimal for this problem since we must inspect every element), it uses O(n) extra space for the temporary list. The problem explicitly requires an in-place solution with O(1) extra memory.

The fundamental issue is that we are collecting results externally and copying back, when we should be able to rearrange elements directly inside the original array. Since the array is sorted, duplicates sit right next to each other. We do not need to search for them — we just need to skip over them while writing unique values to the front of the array.

The key insight: we can use two pointers within the same array. One pointer tracks where to write the next unique element (slow), and the other scans ahead looking for new values (fast). This eliminates the need for any extra storage.

Optimal Approach - Two Pointers In-Place

Intuition

We maintain two pointers that both walk through the same array:

  • Slow pointer (slow): marks the position where the next unique element should be placed. Everything at and before slow is part of the final unique sequence.
  • Fast pointer (fast): scans ahead through the array looking for elements that differ from nums[slow].

Whenever fast finds a value different from nums[slow], we know we have discovered a new unique element. We increment slow and copy the new value there. If the values are the same, fast simply moves forward, skipping the duplicate.

Because the array is sorted, all copies of the same number are grouped together. So once fast moves past a group of duplicates, it will never encounter that value again. This guarantees that every unique value is written to the front of the array exactly once.

Imagine two friends walking through a hallway of portraits sorted by artist. The first friend (slow) stands at the gallery entrance, ready to accept paintings. The second friend (fast) walks ahead, scanning each portrait. When the second friend finds a painting by a new artist, they hand it to the first friend who places it in the next open spot. If the artist is the same as the last accepted painting, the second friend just keeps walking.

Step-by-Step Explanation

Let's trace through with nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]:

Step 1: Initialize slow = 0, fast = 1. nums[slow] = 0 is the first unique element.

Step 2: fast = 1, nums[1] = 0. Compare with nums[slow] = 0. Equal — duplicate. Move fast to 2.

Step 3: fast = 2, nums[2] = 1. Compare with nums[slow] = 0. Different! New unique found. Increment slow to 1, write nums[1] = 1. nums = [0, 1, 1, 1, 1, 2, 2, 3, 3, 4].

Step 4: fast = 3, nums[3] = 1. Compare with nums[slow] = 1. Equal — duplicate. Move fast to 4.

Step 5: fast = 4, nums[4] = 1. Compare with nums[slow] = 1. Equal — duplicate. Move fast to 5.

Step 6: fast = 5, nums[5] = 2. Compare with nums[slow] = 1. Different! Increment slow to 2, write nums[2] = 2. nums = [0, 1, 2, 1, 1, 2, 2, 3, 3, 4].

Step 7: fast = 6, nums[6] = 2. Compare with nums[slow] = 2. Equal — duplicate. Move fast to 7.

Step 8: fast = 7, nums[7] = 3. Compare with nums[slow] = 2. Different! Increment slow to 3, write nums[3] = 3. nums = [0, 1, 2, 3, 1, 2, 2, 3, 3, 4].

Step 9: fast = 8, nums[8] = 3. Compare with nums[slow] = 3. Equal — duplicate. Move fast to 9.

Step 10: fast = 9, nums[9] = 4. Compare with nums[slow] = 3. Different! Increment slow to 4, write nums[4] = 4. nums = [0, 1, 2, 3, 4, 2, 2, 3, 3, 4].

Step 11: fast = 10, which is out of bounds. Done. Return slow + 1 = 5.

Two Pointers — In-Place Duplicate Removal — Watch the slow pointer build the unique sequence at the front of the array while the fast pointer scans ahead, skipping over duplicates.

Algorithm

  1. If the array is empty, return 0
  2. Initialize slow = 0 (first unique element is already in place)
  3. For fast from 1 to n - 1:
    • If nums[fast] ≠ nums[slow]:
      • Increment slow
      • Set nums[slow] = nums[fast]
  4. Return slow + 1 (the count of unique elements)

Code

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        int slow = 0;
        
        for (int fast = 1; fast < nums.size(); fast++) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
        }
        
        return slow + 1;
    }
};
class Solution:
    def removeDuplicates(self, nums: list[int]) -> int:
        if not nums:
            return 0
        
        slow = 0
        
        for fast in range(1, len(nums)):
            if nums[fast] != nums[slow]:
                slow += 1
                nums[slow] = nums[fast]
        
        return slow + 1
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        
        int slow = 0;
        
        for (int fast = 1; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
        }
        
        return slow + 1;
    }
}

Complexity Analysis

Time Complexity: O(n)

The fast pointer scans through the entire array exactly once, performing a constant-time comparison at each step. The slow pointer advances at most k times (where k is the number of unique elements), and each write is O(1). Total work: O(n).

Space Complexity: O(1)

We use only two integer variables (slow and fast). No extra arrays, hash maps, or sets are allocated. The rearrangement happens entirely in-place within the original array. This is the optimal space usage for this problem.