How do you remove duplicates from a sorted array in place?
Short answer: Because the array is sorted, duplicates are next to each other. Keep a write index k pointing at the last unique value; for each new element that differs from arr[k], increment k and copy it there. The new length is k + 1.
#include <stddef.h>
size_t remove_duplicates(int *arr, size_t n)
{
if (n == 0) return 0;
size_t k = 0; /* arr[0..k] are the unique values */
for (size_t i = 1; i < n; i++) {
if (arr[i] != arr[k]) {
k++;
arr[k] = arr[i];
}
}
return k + 1; /* new length */
}
/* {1, 3, 3, 5, 5, 6, 9} -> {1, 3, 5, 6, 9}, returns 5 */
Dry run
| i | arr[i] | arr[k] | action | unique part |
|---|---|---|---|---|
| 1 | 3 | 1 | k=1, copy | 1 3 |
| 2 | 3 | 3 | skip | 1 3 |
| 3 | 5 | 3 | k=2, copy | 1 3 5 |
| 4 | 5 | 5 | skip | 1 3 5 |
| 5 | 6 | 5 | k=3, copy | 1 3 5 6 |
| 6 | 9 | 6 | k=4, copy | 1 3 5 6 9 |
Report the new length. A common slip is printing the original size after removing duplicates. The caller needs k + 1; the values after that index are leftovers and should be ignored.
Complexity: O(n) time, O(1) extra space. Each element is read once and written at most once.
Follow-ups
- Unsorted array: sort first (O(n log n)), or use a hash set / bitmap of seen values (O(n) time, O(n) memory).
- Allow each value at most twice: compare with
arr[k-1]instead ofarr[k]. - Do not change order of first occurrences in an unsorted array: hash set of seen values while copying.