Remove Duplicates from a Sorted Array (In Place)
Given an array sorted in ascending order, remove the duplicates in place so each value appears once, keeping the original order. Return the new length. Elements beyond the new length don't matter. Use O(1) extra memory.
Example: {1, 3, 3, 5, 5, 6, 9} → length 5, array starts {1, 3, 5, 6, 9}.
Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.
Duplicates are always next to each other in a sorted array. Keep a "write" index for the last unique value, and copy an element forward only when it differs from that value.
#include <stdio.h>
#include <stddef.h>
#include <string.h>
size_t remove_duplicates_sorted(int *a, size_t n)
{
if (n == 0) return 0;
size_t w = 0; /* index of the last unique value */
for (size_t r = 1; r < n; r++) {
if (a[r] != a[w])
a[++w] = a[r]; /* new value: keep it */
}
return w + 1;
}
This is the read/write two-pointer pattern: r scans every element, w marks the end of the unique prefix. Since equal values are adjacent, comparing with a[w] alone is enough. O(n) time, O(1) memory, one pass, and the relative order is preserved.
Walk-through: {1, 3, 3, 5, 5, 6, 9}
| r | a[r] | a[w] | action | unique prefix |
|---|---|---|---|---|
| 1 | 3 | 1 | copy to a[1] | 1 3 |
| 2 | 3 | 3 | skip | 1 3 |
| 3 | 5 | 3 | copy to a[2] | 1 3 5 |
| 4 | 5 | 5 | skip | 1 3 5 |
| 5 | 6 | 5 | copy to a[3] | 1 3 5 6 |
| 6 | 9 | 6 | copy to a[4] | 1 3 5 6 9 |
Return w + 1 = 5.
Edge cases: empty array (the classic bug is n - 1 underflowing when n is unsigned), one element, all equal, no duplicates.
Follow-ups: allow each value at most twice (compare with a[w - 1]); remove all copies of a given value; for an unsorted array, see Remove Duplicates Using a Hash Table.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
int main(void)
{
int a[] = { 1, 3, 3, 5, 5, 6, 9 };
const int ea[] = { 1, 3, 5, 6, 9 };
CHECK(remove_duplicates_sorted(a, 7) == 5 && memcmp(a, ea, sizeof ea) == 0);
int b[] = { 2, 2, 2, 2 };
CHECK(remove_duplicates_sorted(b, 4) == 1 && b[0] == 2);
int c[] = { 1, 2, 3 };
CHECK(remove_duplicates_sorted(c, 3) == 3 && c[2] == 3);
int d[] = { -3, -3, 0, 0, 0, 7 };
const int ed[] = { -3, 0, 7 };
CHECK(remove_duplicates_sorted(d, 6) == 3 && memcmp(d, ed, sizeof ed) == 0);
CHECK(remove_duplicates_sorted(NULL, 0) == 0);
int e[] = { 42 };
CHECK(remove_duplicates_sorted(e, 1) == 1);
puts(fails ? "Some tests failed" : "All tests passed");
return fails != 0;
}