C Program to Remove Duplicates from Sorted Array

To remove duplicates from a sorted array in C, iterate through the array comparing each element with the next, and copy only unique elements to the front using code like int j = 0; for (int i = 1; i < n; i++) if (arr[i] != arr[j]) arr[++j] = arr[i]; which keeps unique elements at the start.

Examples

Inputarr = {1, 2, 2, 3, 4, 4, 5}, n = 7

OutputUnique elements count = 5, arr = {1, 2, 3, 4, 5}

Inputarr = {1, 1, 1, 1}, n = 4

OutputUnique elements count = 1, arr = {1}

Inputarr = {1, 2, 3, 4, 5}, n = 5

OutputUnique elements count = 5, arr = {1, 2, 3, 4, 5}

How to Think About It

Since the array is sorted, duplicates will be next to each other. We can scan the array once, compare each element with the last unique element found, and copy it forward only if it is different. This way, we keep only unique elements at the start without extra space.

Algorithm

1

Start with the first element as unique and set a pointer j to 0.

2

Loop through the array from the second element to the end.

3

For each element, compare it with the element at position j.

4

If it is different, increment j and copy the current element to position j.

5

After the loop, j + 1 is the count of unique elements.

6

Return or print the unique elements from index 0 to j.

Code

c

#include <stdio.h>

int removeDuplicates(int arr[], int n) {
    if (n == 0) return 0;
    int j = 0;
    for (int i = 1; i < n; i++) {
        if (arr[i] != arr[j]) {
            j++;
            arr[j] = arr[i];
        }
    }
    return j + 1;
}

int main() {
    int arr[] = {1, 2, 2, 3, 4, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int newLength = removeDuplicates(arr, n);
    printf("Unique elements count = %d\n", newLength);
    printf("Array after removing duplicates: ");
    for (int i = 0; i < newLength; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

Output

Unique elements count = 5
Array after removing duplicates: 1 2 3 4 5 

Dry Run

Let's trace the array {1, 2, 2, 3, 4, 4, 5} through the code

1

Initialize

j = 0, arr = {1, 2, 2, 3, 4, 4, 5}

2

i = 1, compare arr[1] and arr[0]

2 != 1, increment j to 1, arr[1] = 2

3

i = 2, compare arr[2] and arr[1]

2 == 2, no change

4

i = 3, compare arr[3] and arr[1]

3 != 2, increment j to 2, arr[2] = 3

5

i = 4, compare arr[4] and arr[2]

4 != 3, increment j to 3, arr[3] = 4

6

i = 5, compare arr[5] and arr[3]

4 == 4, no change

7

i = 6, compare arr[6] and arr[3]

5 != 4, increment j to 4, arr[4] = 5

i	j	arr after operation
1	1	{1, 2, 2, 3, 4, 4, 5}
2	1	{1, 2, 2, 3, 4, 4, 5}
3	2	{1, 2, 3, 3, 4, 4, 5}
4	3	{1, 2, 3, 4, 4, 4, 5}
5	3	{1, 2, 3, 4, 4, 4, 5}
6	4	{1, 2, 3, 4, 5, 4, 5}

Why This Works

Step 1: Start with first element

We consider the first element unique by default and set j = 0 to track the last unique element's index.

Step 2: Compare and copy unique elements

For each element, if it differs from arr[j], we increment j and copy the new unique element to arr[j].

Step 3: Return count of unique elements

After processing, j + 1 gives the count of unique elements, and the first j + 1 elements in the array are unique.

Alternative Approaches

Using extra array

c

#include <stdio.h>

int removeDuplicatesExtra(int arr[], int n, int result[]) {
    if (n == 0) return 0;
    int j = 0;
    result[j] = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] != arr[i-1]) {
            j++;
            result[j] = arr[i];
        }
    }
    return j + 1;
}

int main() {
    int arr[] = {1, 2, 2, 3, 4, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result[n];
    int newLength = removeDuplicatesExtra(arr, n, result);
    printf("Unique elements count = %d\n", newLength);
    printf("Array after removing duplicates: ");
    for (int i = 0; i < newLength; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
    return 0;
}

Uses extra space for a new array, simpler but uses O(n) space.

Using two pointers without copying

c

#include <stdio.h>

int removeDuplicatesNoCopy(int arr[], int n) {
    if (n == 0) return 0;
    int i = 0, j = 1;
    while (j < n) {
        if (arr[i] != arr[j]) {
            i++;
            arr[i] = arr[j];
        }
        j++;
    }
    return i + 1;
}

int main() {
    int arr[] = {1, 2, 2, 3, 4, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int newLength = removeDuplicatesNoCopy(arr, n);
    printf("Unique elements count = %d\n", newLength);
    printf("Array after removing duplicates: ");
    for (int i = 0; i < newLength; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

Uses two pointers to overwrite duplicates, similar to main method but with different pointer names.

Complexity: O(n) time, O(1) space

Time Complexity

The program loops through the array once, comparing adjacent elements, so it runs in linear time O(n).

Space Complexity

It modifies the array in place without extra arrays, so space complexity is O(1).

Which Approach is Fastest?

The in-place method is fastest and most memory efficient compared to using extra arrays.

Approach	Time	Space	Best For
In-place overwrite	O(n)	O(1)	Memory efficient, fast
Extra array copy	O(n)	O(n)	Simpler code, uses more memory
Two pointers variant	O(n)	O(1)	Similar to in-place, different pointer style