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
Example 1 Several duplicates
- Input
[1, 1, 2, 2, 3]- Output
3, [1, 2, 3]
Checks normal in-place compaction.
Example 2 All equal
- Input
[5, 5, 5]- Output
1, [5]
Checks repeated values at every position.
Example 3 Already unique
- Input
[1, 2, 3]- Output
3, [1, 2, 3]
Confirms valid input remains unchanged.
Hints Optional
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
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

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
writeinstead ofwrite + 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 EndReuse the read and write pointer model.