Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Remove Duplicates from a Sorted Array

Use read and write pointers to keep one copy of each value in place.

EasyArraysPattern: two pointers, in place compaction

Problem statement

Given a sorted array, keep one copy of each distinct value at the beginning of the same array. Return the number of distinct values.

For [1, 1, 2, 2, 3], return 3. The first three positions become [1, 2, 3].

Constraints & requirements

INPUT
A sorted integer array
CHANGE
Update the same array
RETURN
Length of the unique prefix

Examples 3 test cases

  1. Example 1 Several duplicates

    Input
    [1, 1, 2, 2, 3]
    Output
    3, [1, 2, 3]

    Checks normal in-place compaction.

  2. Example 2 All equal

    Input
    [5, 5, 5]
    Output
    1, [5]

    Checks repeated values at every position.

  3. Example 3 Already unique

    Input
    [1, 2, 3]
    Output
    3, [1, 2, 3]

    Confirms valid input remains unchanged.

Hints Optional

Hints become more specific one step at a time.
01Use the sorted guarantee

Duplicates are adjacent, so compare the current read value with the last accepted value.

02Separate read and write

Read inspects every value. Write marks the last position of the unique prefix.

03Return a length

If write is the last valid index, the number of valid values is write + 1.

How to think before coding

Sorted order means a repeated value cannot become new again later. Define write as the index of the last kept unique value and read as the next position to inspect. Advance write only when the read value differs. Because write never moves beyond read, copying cannot destroy unread input. The return is a count, so use write+1, not write.

Brute force and the improvement

Build a new list of unique values, then copy them back: O(n) time and O(n) extra space. It does not meet the constant-space goal. Removing each duplicate by shifting the remaining elements can cost O(n²) time. Read/write compaction avoids repeated shifts.

Intuition

Because the array is sorted, equal values are next to one another. A read pointer scans every value. A write pointer marks the position where the next distinct value belongs.

The invariant is that positions 0 through write already contain the unique prefix.

Java solution

Java
public static int removeDuplicates(int[] values) {
    // An empty array has no unique prefix.
    if (values == null || values.length == 0) {
        return 0;
    }

    // The first value is already kept. Write is the last kept index, not a count.
    int write = 0;
    for (int read = 1; read < values.length; read++) {
        // Sorted input groups duplicates: compare with the last unique value.
        if (values[read] != values[write]) {
            write++; // Reserve a new slot only for a new distinct value.
            values[write] = values[read];
        }
    }
    return write + 1; // Last kept index + 1 is the unique count.
}

Dry run

Numbered illustrated dry run for Remove Duplicates from a Sorted Array; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

For [1, 1, 2, 2, 3], start with write = 0 and unique prefix [1].

Read index Read value Action Write index Unique prefix
1 1 Skip duplicate 0 [1]
2 2 Advance write and copy 1 [1, 2]
3 2 Skip duplicate 1 [1, 2]
4 3 Advance write and copy 2 [1, 2, 3]

Return 3. Values beyond this prefix are irrelevant; they need not be erased. Writing never destroys an unread value because write <= read.

Complexity

Time is O(n) and extra space is O(1).

Common mistakes

  • Returning write instead of write + 1
  • Comparing with the previous read position instead of the last unique value
  • Creating another array when the problem asks for an in place update

Practice next

Next lessonMove Zeroes to the End

Reuse the read and write pointer model.

Back to Arrays →