Remove Duplicates from Sorted Array

Difficulty: Easy

Problem

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. Return k after placing the final result in the first k slots of nums.

Example

Input: nums = [1, 1, 2]
Output: 2, nums = [1, 2, _]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively. It does not matter what you leave beyond k.

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)