C Array Exercises: Remove Duplicates from a Sorted Array

Contiguous C array memory cells with two-pointer manipulation.
Contiguous C array memory cells with two-pointer manipulation.

Problem Statement

Given a sorted array of N integers, remove repeated values in-place and print the new length followed by the unique elements in sorted order. Do not allocate a second array.

Two-Pointer Compaction

The input is sorted in nondecreasing order, so equal values are adjacent. Keep the first occurrence of each value in the original array.

  1. Keep a read index for the next input element and a write index for the next unique slot.
  2. When the value differs from the last retained value, copy it to arr[write] and advance the write index.
  3. Print the retained length and only that prefix of the array.

Boundary Cases

An array with one value remains unchanged. If every value is equal, retain one element. Negative values and zero are valid.

Complexity & Editorial

Maintain a Unique Prefix

Start with write = 1 because N is at least one. Before each iteration, arr[0..write-1] contains exactly the unique values seen so far. Compare arr[read] with arr[write - 1]: if equal, skip it; otherwise copy it to arr[write] and increment write.

Why Overwriting Is Safe

The write index never moves ahead of the read index, so compaction cannot overwrite unread input. Sorted order makes all duplicates adjacent. Print only the retained prefix: the remaining cells are not part of the result.

Starter Code

#include <stdio.h>

#define MAX_N 1000

int remove_duplicates(int arr[], int n) {
    // TODO: Compact unique values into arr[0..write-1] and return write.
    (void)arr;
    return n;
}

int main(void) {
    int n;
    if (scanf("%d", &n) != 1 || n < 1 || n > MAX_N) return 1;
    int arr[MAX_N];
    for (int i = 0; i < n; ++i) {
        if (scanf("%d", &arr[i]) != 1 || arr[i] < -1000 || arr[i] > 1000) return 1;
        if (i > 0 && arr[i] < arr[i - 1]) return 1;
    }
    int length = remove_duplicates(arr, n);
    printf("%d\n", length);
    for (int i = 0; i < length; ++i) {
        printf("%d%c", arr[i], i == length - 1 ? '\n' : ' ');
    }
    return 0;
}

Frequently Asked Questions

Does this work on an unsorted array?

Not as written. The algorithm relies on equal values being adjacent in sorted input.

Does the physical array become smaller?

No. The function returns a logical length. Only the prefix of that length contains the result.

What happens when all values are equal?

The first value is retained and the returned length is one.

Related exercises