C program to delete all duplicate elements from an array

In C programming, arrays are a fundamental data structure, and managing their elements often involves various operations such as deleting duplicates. This article will guide you through writing a C program to delete all duplicate elements from an array, providing explanations and sample code for better understanding.

Steps to Delete Duplicate Elements

To delete all duplicate elements from an array, we can follow these steps:

1. Input the Array: Read the array elements from the user.
2. Identify Duplicate Elements: Check each element to determine if it is a duplicate.
3. Delete Duplicates: Remove the duplicate elements and shift the remaining elements to maintain the array's integrity.

We'll discuss one comprehensive method to achieve this using a nested loop.

Using Nested Loops to Identify and Remove Duplicates

#include <stdio.h>

int main() {
    int size;
    printf("Enter the size of the array: ");
    scanf("%d", &size);

    int arr[size];
    printf("Enter %d elements -\n", size);
    for (int i = 0; i < size; i++) {
        scanf("%d", &arr[i]);
    }

    // Process to remove duplicates
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; ) {
            if (arr[i] == arr[j]) {
                // Shift elements to the left
                for (int k = j; k < size - 1; k++) {
                    arr[k] = arr[k + 1];
                }
                size--; // Reduce the size of the array
            } else {
                j++;
            }
        }
    }

    // Printing the array after removing duplicates
    printf("Array after removing duplicates: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

Explanation:

1. Input the Array: The user inputs the size of the array and the elements.
2. Identify Duplicate Elements: The program uses two nested loops. The outer loop iterates through each element, and the inner loop checks if the current element is equal to any subsequent element.
3. Delete Duplicates: When a duplicate is found, the inner loop shifts all subsequent elements to the left, effectively overwriting the duplicate. The size of the array is reduced accordingly.
4. Print the Result: Finally, the program prints the array after all duplicates have been removed.

Advantages:

• Simple and straightforward to implement.
• No additional memory required apart from the input array.

Disadvantages:

• Time complexity is O(n^2), making it inefficient for large arrays.

Optimization: Using a Frequency Array (Alternative Approach)

While the above method works well for small arrays, it can be inefficient for larger arrays due to its O(n^2) time complexity. A more efficient method involves using an auxiliary array to track the frequency of each element.

#include <stdio.h>

#define MAX 100

int main() {
    int size;
    printf("Enter the size of the array: ");
    scanf("%d", &size);

    int arr[size];
    printf("Enter %d elements -\n", size);
    for (int i = 0; i < size; i++) {
        scanf("%d", &arr[i]);
    }

    int freq[MAX] = {0}; // Frequency array, assuming elements range from 0 to MAX-1
    int uniqueArr[size]; // Array to store unique elements
    int uniqueSize = 0;  // Size of the unique array

    // Populate frequency array and create array with unique elements
    for (int i = 0; i < size; i++) {
        if (freq[arr[i]] == 0) {
            uniqueArr[uniqueSize++] = arr[i];
        }
        freq[arr[i]]++;
    }

    // Copy unique elements back to original array
    for (int i = 0; i < uniqueSize; i++) {
        arr[i] = uniqueArr[i];
    }
    size = uniqueSize; // Update the size to the number of unique elements

    // Printing the array after removing duplicates
    printf("Array after removing duplicates: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

Explanation:

1. Input the Array: The user inputs the size of the array and the elements.
2. Frequency Array: The program initializes a frequency array to zero and an array to store unique elements.
3. Populate Frequency Array: The program iterates through the input array, populating the frequency array and simultaneously building the unique array.
4. Copy Unique Elements: The unique elements are copied back to the original array, and the size is updated.
5. Print the Result: Finally, the program prints the array after all duplicates have been removed.

Advantages:

• More efficient with a time complexity of O(n).
• Suitable for larger arrays compared to the nested loop method.

Disadvantages:

• Requires additional memory for the frequency and unique arrays.
• Assumes a known range of possible values in the array.

Output

Enter the size of the array: 10
Enter 10 elements -
1
2
1
2
3
4
5
6
7
7
Array after removing duplicates: 1 2 3 4 5 6 7