Remove Duplicates from Sorted Array

Difficulty: Easy

Problem

You receive an integer array nums that is sorted in non-decreasing order. Squeeze out the repeated values directly inside nums so that each distinct value is kept just once, still in its original order, packed at the front of the array. Return k, the number of distinct values, which is how many leading slots hold the final result.

Example

Input: nums = [0, 0, 3, 3, 3, 7]
Output: 3, nums = [0, 3, 7, _, _, _]
Explanation: The function returns k = 3, and the first three slots of nums hold 0, 3 and 7 in that order. Whatever sits in the slots after index k does not matter.

Brute-force approach

Use a hash set to track unique elements, then overwrite the array.

Steps

  1. Create an empty set to store unique elements
  2. Traverse the array and add each element to the set
  3. Copy elements from the set back to the array
  4. Return the size of the set

Time complexity: O(n) · Space complexity: O(n)

Trade-offs

  • Uses O(n) extra space for the set
  • Violates the in-place requirement
  • Not needed since array is already sorted

Optimal approach

Key insight: Since the array is sorted, duplicates are adjacent. Use pointer k to track where the next unique element should go. When nums[i] differs from nums[i-1], it's a new unique element!

Use two pointers: one for the current position, one for the next unique position.

Steps

  1. If array is empty, return 0
  2. Initialize k = 1 (first element is always unique)
  3. Traverse from index 1 to end
  4. If current != previous, place at k and increment k
  5. Return k as the count of unique elements

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

Pseudocode

function removeDuplicates(nums):
    if nums is empty: return 0
    k = 1  // pointer for next unique position
    for i from 1 to length(nums):
        if nums[i] != nums[i-1]:
            nums[k] = nums[i]
            k++
    return k

Hints

  • Since array is sorted, duplicates are adjacent
  • Use a pointer k to track where next unique element should go
  • Compare each element with the previous one

Complexity questions

What is the time complexity of the hash set approach?

O(n). O(n) to add to set + O(n) to copy back = O(n).

What is the space complexity of the hash set approach?

O(n). In the worst case (all unique), the set holds n elements.

What is the time complexity of the two pointers approach?

O(n). Single pass through the array = O(n).

What is the space complexity of the two pointers approach?

O(1). Only two variables (k, i) used regardless of input size.

Check your understanding of Remove Duplicates from Sorted Array

Why is it important that the array is sorted?

Duplicates are guaranteed to be adjacent. In a sorted array, all duplicates are next to each other, so we only need to compare adjacent elements.

For [0,0,1,1,1,2,2,3,3,4], what should the function return?

5, with first 5 elements being [0,1,2,3,4]. There are 5 unique elements (0,1,2,3,4), so return 5 and place them at the start.

What happens to elements after position k?

It doesn't matter what they contain. The problem only cares about the first k elements containing unique values.

Related problems

Keep practising