10. Remove Duplicates from a Sorted Array

Difficulty:EasyPattern:Read/Write Two PointersTime:O(n)Space:O(1)

Given a sorted array, remove duplicate values in place such that each unique element appears only once. Return the number of unique elements.

How It Works & Algorithmic Design

This problem uses a Read/Write Two-Pointer Pattern:

Precondition: Because the array is sorted, all duplicate elements are contiguous.
Pointer Definitions:
- write: Index where the next unique value should be placed (starts at 1).
- read: Index used to scan through the array (starts at 1).
Scanning Logic: Compare arr[read] with the element right before it (arr[read - 1]):
- If arr[read] !== arr[read - 1], a new unique element has been found.
- Write this unique element to arr[write], then increment write (write++).
Result: The value of write equals the total count of unique elements, and the sub-array arr[0 ... write - 1] contains those unique values in order.

Why This Approach Works Best

It modifies the array in-place without creating a new set or duplicate array, running in $O(n)$ time and $O(1)$ extra space.

Example Walkthrough

Input Array: [0, 0, 1, 1, 1, 2, 2, 3]

Sorted array with duplicate groups.

Write Operations: arr[1]=1 -> arr[2]=2 -> arr[3]=3

Overwrites duplicate positions with newly discovered unique values.

Modified Sub-Array: [0, 1, 2, 3, ...]

Unique elements shifted to the front.

Return Count: 4

4 unique elements found.

Answer: In-place deduplication

function removeDuplicates(arr) {
  if (!arr || arr.length === 0) return 0;
  let write = 1;
  for (let read = 1; read < arr.length; read++) {
    if (arr[read] !== arr[read - 1]) {
      arr[write] = arr[read];
      write++;
    }
  }
  return write;
}

💡 Use read and write pointers to overwrite duplicate entries in a single pass.

Key Takeaways

Contiguous grouping in sorted arrays makes duplicate detection straightforward.
The read pointer scans elements while the write pointer places unique values.
Achieves $O(n)$ time complexity and $O(1)$ space complexity by modifying the array in-place.