</>EmbeddedInterview

How do you remove duplicates from a sorted array in place?

EasyArrays & Strings (Coding Round)

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 of arr[k].
  • Do not change order of first occurrences in an unsorted array: hash set of seen values while copying.