Delete Duplicate Elements from an Array

📚 In this tutorial, you will learn:

What is array deduplication
Different approaches to remove duplicates
Using sorting and using hash-based approach
In-place removal of duplicates
Time and space complexity analysis

Introduction to Array Deduplication

Deleting duplicate elements from an array means removing all occurrences of elements that appear more than once, keeping only the first occurrence. The result is an array with unique elements only.

Key characteristics of array deduplication:

In-place vs extra space: Can be done with or without using extra memory
Sorted vs unsorted: Sorted arrays are easier to deduplicate
Order preservation: May or may not preserve original order
Applications: Data cleaning, removing redundant data, improving efficiency

💡 Example: For array [1, 2, 2, 3, 4, 4, 5], after removing duplicates we get [1, 2, 3, 4, 5].

C Program to Delete Duplicate Elements

#include <stdio.h>
#include <stdlib.h>

// Function to swap two elements
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Approach 1: Remove duplicates from sorted array (in-place)
// Returns new size of array
int removeDuplicatesSorted(int arr[], int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    
    int j = 0; // Index for unique elements
    
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] != arr[i + 1]) {
            arr[j++] = arr[i];
        }
    }
    arr[j++] = arr[n - 1];
    
    return j;
}

// Approach 2: Remove duplicates from unsorted array (using sorting)
int removeDuplicatesUnsorted(int arr[], int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    
    // Sort the array first
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
    
    // Now remove duplicates from sorted array
    return removeDuplicatesSorted(arr, n);
}

// Approach 3: Remove duplicates preserving original order (using extra array)
int removeDuplicatesPreserveOrder(int arr[], int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    
    int *temp = (int *)malloc(n * sizeof(int));
    int j = 0;
    
    for (int i = 0; i < n; i++) {
        int isDuplicate = 0;
        for (int k = 0; k < j; k++) {
            if (arr[i] == temp[k]) {
                isDuplicate = 1;
                break;
            }
        }
        if (!isDuplicate) {
            temp[j++] = arr[i];
        }
    }
    
    // Copy back to original array
    for (int i = 0; i < j; i++) {
        arr[i] = temp[i];
    }
    
    free(temp);
    return j;
}

// Approach 4: Remove duplicates preserving order (in-place, O(n²))
int removeDuplicatesInPlace(int arr[], int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    
    int newSize = n;
    
    for (int i = 0; i < newSize; i++) {
        for (int j = i + 1; j < newSize; j++) {
            if (arr[i] == arr[j]) {
                // Shift all elements left by one
                for (int k = j; k < newSize - 1; k++) {
                    arr[k] = arr[k + 1];
                }
                newSize--;
                j--; // Check the new element at this position
            }
        }
    }
    
    return newSize;
}

// Function to print the array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Driver program to test duplicate removal
int main() {
    int arr1[] = {1, 2, 2, 3, 4, 4, 5, 5, 5, 6};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    
    printf("Original array: ");
    printArray(arr1, n1);
    
    // Test Approach 1 (Sorted array)
    int newSize1 = removeDuplicatesSorted(arr1, n1);
    printf("After removing duplicates (sorted): ");
    printArray(arr1, newSize1);
    printf("New size: %d\n\n", newSize1);
    
    int arr2[] = {7, 2, 5, 2, 8, 5, 9, 1, 7, 3};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    
    printf("Original array: ");
    printArray(arr2, n2);
    
    // Test Approach 2 (Unsorted with sorting)
    int *arr2Copy = (int *)malloc(n2 * sizeof(int));
    for (int i = 0; i < n2; i++) arr2Copy[i] = arr2[i];
    int newSize2 = removeDuplicatesUnsorted(arr2Copy, n2);
    printf("After removing duplicates (with sorting): ");
    printArray(arr2Copy, newSize2);
    printf("New size: %d\n", newSize2);
    free(arr2Copy);
    
    // Test Approach 3 (Preserving order)
    int *arr3Copy = (int *)malloc(n2 * sizeof(int));
    for (int i = 0; i < n2; i++) arr3Copy[i] = arr2[i];
    int newSize3 = removeDuplicatesPreserveOrder(arr3Copy, n2);
    printf("After removing duplicates (preserving order): ");
    printArray(arr3Copy, newSize3);
    printf("New size: %d\n", newSize3);
    free(arr3Copy);
    
    // Test Approach 4 (In-place O(n²))
    int *arr4Copy = (int *)malloc(n2 * sizeof(int));
    for (int i = 0; i < n2; i++) arr4Copy[i] = arr2[i];
    int newSize4 = removeDuplicatesInPlace(arr4Copy, n2);
    printf("After removing duplicates (in-place): ");
    printArray(arr4Copy, newSize4);
    printf("New size: %d\n", newSize4);
    free(arr4Copy);
    
    return 0;
}

Sample Output

Original array: 1 2 2 3 4 4 5 5 5 6 
After removing duplicates (sorted): 1 2 3 4 5 6 
New size: 6

Original array: 7 2 5 2 8 5 9 1 7 3 
After removing duplicates (with sorting): 1 2 3 5 7 8 9 
New size: 7
After removing duplicates (preserving order): 7 2 5 8 9 1 3 
New size: 7
After removing duplicates (in-place): 7 2 5 8 9 1 3 
New size: 7

Program Explanation

The program demonstrates four different approaches to remove duplicates:

Remove Duplicates from Sorted Array (O(n) time, O(1) space):
- Works only when the array is already sorted
- Uses two pointers: one for unique elements, one for traversal
- Compares adjacent elements and copies unique ones
- Most efficient approach for sorted arrays
Remove Duplicates from Unsorted Array using Sorting (O(n log n) time, O(1) space):
- First sorts the array using bubble sort
- Then removes duplicates from the sorted array
- Does not preserve original order
Remove Duplicates Preserving Order (O(n²) time, O(n) space):
- Uses an extra array to store unique elements
- Checks if each element already exists in the temp array
- Preserves the original order of elements
Remove Duplicates In-Place (O(n²) time, O(1) space):
- Removes duplicates without using extra memory
- Shifts elements left when a duplicate is found
- Preserves original order
- Simple but inefficient for large arrays

Step-by-Step Approach

Step	Action	Explanation
1	Identify Duplicates	Check if any element appears more than once
2	Choose Approach	Select method based on requirements (order preservation, space constraints)
3	Remove Duplicates	Apply the chosen algorithm
4	Update Array	Resize or return new size of the array

Algorithm for Removing Duplicates from Sorted Array

If array size is 0 or 1, return n
Initialize j = 0 for unique elements
For i = 0 to n-2:
- If arr[i] != arr[i+1], copy arr[i] to arr[j] and increment j
Copy the last element arr[n-1] to arr[j]
Return j as the new size

Time & Space Complexity

Approach	Time Complexity	Space Complexity	Order Preserved
Sorted Array	O(n)	O(1)	✅ Yes
Sort + Deduplicate	O(n log n)	O(1)	❌ No
Extra Array	O(n²)	O(n)	✅ Yes
In-place O(n²)	O(n²)	O(1)	✅ Yes

📊 Recommendation:

For sorted arrays: Use the two-pointer approach (O(n) time, O(1) space)
For unsorted arrays without order preservation: Sort first then remove duplicates
For unsorted arrays with order preservation: Use extra array or in-place shifting

💻 Practice Exercise

Challenge 1: Modify the program to remove duplicates without sorting and without using extra array.

Challenge 2: Implement duplicate removal for an array of strings (case-insensitive).

Challenge 3: Remove duplicates from a sorted array in-place using two-pointer technique.

🔍 Click to Show Solution for Challenge 1

// Remove duplicates without sorting and without extra array
// Using nested loops and shifting
int removeDuplicatesNoSortNoExtra(int arr[], int n) {
    int newSize = n;
    for (int i = 0; i < newSize; i++) {
        for (int j = i + 1; j < newSize; j++) {
            if (arr[i] == arr[j]) {
                for (int k = j; k < newSize - 1; k++) {
                    arr[k] = arr[k + 1];
                }
                newSize--;
                j--;
            }
        }
    }
    return newSize;
}

🔍 Click to Show Solution for Challenge 3

// Remove duplicates from sorted array using two-pointer technique
int removeDuplicatesTwoPointer(int arr[], int n) {
    if (n == 0 || n == 1) return n;
    int j = 0;
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] != arr[i + 1]) {
            arr[j++] = arr[i];
        }
    }
    arr[j++] = arr[n - 1];
    return j;
}

Frequently Asked Questions

1. What is the most efficient way to remove duplicates?

The most efficient approach depends on your requirements:

If the array is sorted: Two-pointer technique (O(n) time, O(1) space)
If order doesn't matter: Sort first then remove duplicates (O(n log n) time, O(1) space)
If order matters: Use extra array (O(n²) time, O(n) space) or in-place shifting

2. Can we remove duplicates in O(n) time without extra space?

Yes, but only if the array is already sorted. For unsorted arrays, O(n) time with O(1) space is not possible using comparison-based methods. You would need a hash table (O(n) space) for O(n) time.

3. Does the in-place approach preserve the original order?

The in-place shifting approach (removeDuplicatesInPlace) preserves the original order of elements. However, the sorting-based approach does not preserve order. The extra array approach also preserves order.

4. How can I remove duplicates from a character array?

The same algorithms work for character arrays. Just change the data type from int to char. For case-insensitive removal, convert all characters to lowercase or uppercase before comparison.

5. What are real-world applications of duplicate removal?

Duplicate removal is used in:

Data cleaning and preprocessing
Database deduplication
Removing redundant data from logs
Memory optimization in embedded systems
Finding unique elements in a dataset

💡 Pro Tip: Always consider whether you need to preserve the original order before choosing a duplicate removal approach. If not, sorting-based methods are more efficient.

Previous Topic: -->> Kth Smallest Element in C || Next topic: -->> Rearrange Positive and Negative Numbers

37. Delete Duplicate Elements from an Array in C

Introduction to Array Deduplication

C Program to Delete Duplicate Elements

Sample Output

Program Explanation

Step-by-Step Approach

Algorithm for Removing Duplicates from Sorted Array

Time & Space Complexity

💻 Practice Exercise

Frequently Asked Questions

1. What is the most efficient way to remove duplicates?

2. Can we remove duplicates in O(n) time without extra space?

3. Does the in-place approach preserve the original order?

4. How can I remove duplicates from a character array?

5. What are real-world applications of duplicate removal?

Get in touch

Introduction to Array Deduplication

C Program to Delete Duplicate Elements

Sample Output

Program Explanation

Step-by-Step Approach

Algorithm for Removing Duplicates from Sorted Array

Time & Space Complexity

💻 Practice Exercise

Frequently Asked Questions

1. What is the most efficient way to remove duplicates?

2. Can we remove duplicates in O(n) time without extra space?

3. Does the in-place approach preserve the original order?

4. How can I remove duplicates from a character array?

5. What are real-world applications of duplicate removal?

📖 Related Tutorials