easyArray ProblemsJava

Remove Duplicates From a Sorted Array In Place

Remove duplicates from a sorted array in place and return the count of unique elements.

Quick Answer

Because the array is sorted, duplicates sit next to each other. Keep a slow write pointer at the last unique value and a fast read pointer scanning ahead. When the read pointer finds a value different from the last unique one, advance the write pointer and copy it there. The write pointer's final position gives the unique count.

Problem Statement

Given an array sorted in non-decreasing order, remove the duplicates in place so each distinct value appears only once. The relative order of the kept values stays the same, and the first part of the array should hold the unique values.

Return the number of unique elements k; the first k slots of the array then hold those uniques. Because the array is sorted, equal values are always adjacent.

Input: A sorted array arr of length n (non-decreasing).

Output: The count k of unique elements; arr[0..k-1] holds them in order.

Examples

Example 1
Input:  [1, 1, 2, 3, 3]
Output: 3 -> [1, 2, 3]

Three distinct values 1, 2, 3 remain; the front of the array holds them.

Example 2
Input:  [1, 2, 2, 2, 3, 4, 4]
Output: 4 -> [1, 2, 3, 4]

The repeated 2s and 4s collapse, leaving four unique values.

Constraints

  • 0 <= n <= 10^6
  • Input is sorted in non-decreasing order; extra space must be O(1)

Think Before You Code

Reveal the questions to ask yourself first
  • Why does the array being sorted make duplicates easy to spot?
  • Which pointer writes the unique values and which one scans ahead?
  • What condition tells you a value is new rather than a repeat?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
In a sorted array, any duplicate is right next to its twin — you only compare neighbours.
Hint 2
Keep a slow pointer `write` marking the last unique value, and a fast pointer `read` scanning forward.
Hint 3
When `arr[read] != arr[write]`, do `write++` and copy `arr[write] = arr[read]`. Return `write + 1`.

Approach

Reveal the step-by-step approach

Compact unique values toward the front with two pointers.

  1. If the array is empty, return 0.
  2. Set write = 0 (index of the last unique value written).
  3. For read from 1 to n - 1:
    • If arr[read] != arr[write], then write++ and arr[write] = arr[read].
  4. Return write + 1 — the number of unique elements now sitting in arr[0..write].

Because the array is sorted, a value different from arr[write] is guaranteed to be a new distinct value, so this single pass keeps exactly one copy of each.

Dry Run

Walk through the example step by step

Deduplicating [1, 1, 2, 3, 3]:

read | arr[read] | arr[write] | new? | write | array front
-----+-----------+------------+------+-------+-------------
1    | 1         | 1          | no   | 0     | [1 ...]
2    | 2         | 1          | yes  | 1     | [1, 2 ...]
3    | 3         | 2          | yes  | 2     | [1, 2, 3 ...]
4    | 3         | 3          | no   | 2     | [1, 2, 3 ...]
--------------------------------- k = write + 1 = 3

Solution

Reveal the full Java solution
import java.util.Arrays;

public class RemoveDuplicatesSorted {
    public static int removeDuplicates(int[] arr) {
        if (arr.length == 0) {
            return 0;
        }
        int write = 0;
        for (int read = 1; read < arr.length; read++) {
            if (arr[read] != arr[write]) {
                write++;
                arr[write] = arr[read];
            }
        }
        return write + 1;
    }

    public static void main(String[] args) {
        int[] a = {1, 1, 2, 3, 3};
        int k1 = removeDuplicates(a);
        System.out.println(k1 + " -> " + Arrays.toString(Arrays.copyOf(a, k1))); // 3 -> [1, 2, 3]

        int[] b = {1, 2, 2, 2, 3, 4, 4};
        int k2 = removeDuplicates(b);
        System.out.println(k2 + " -> " + Arrays.toString(Arrays.copyOf(b, k2))); // 4 -> [1, 2, 3, 4]
    }
}

The sorted order is what makes an O(1)-space solution possible: identical values are always adjacent, so comparing the read pointer against the last written unique value is enough to decide whether to keep it. The slow write pointer overwrites the duplicate slots in place, and write + 1 is the final unique count.

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

Common Mistakes

  • Comparing `arr[read]` with `arr[read - 1]` but writing to the wrong index, corrupting the compacted prefix.
  • Returning `write` instead of `write + 1`, giving a count that is off by one.
  • Assuming this works on an unsorted array, where equal values are not adjacent.

Edge Cases to Test

  • Empty array [] returns 0.
  • All elements identical, e.g. [5, 5, 5], returns 1.
  • Already-unique array, e.g. [1, 2, 3], returns n unchanged.

Interview Follow-Ups

  • How would you remove duplicates from an unsorted array instead?
  • How would you allow each value to appear at most twice?
  • How would you also return the removed duplicates?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us