C++ Program to Remove Duplicates from an Array

by

Arrays are a fundamental data structure in programming used to store elements of the same type. One common problem when working with arrays is the presence of duplicate elements. Removing duplicates from an array can help in many applications where unique elements are required. This article will guide you through the implementation of a C++ program to remove duplicates from an array, providing multiple examples to demonstrate various solutions and their outputs.

Prerequisites

Before diving into the implementation, you should have:

  1. Basic understanding of C++ programming.
  2. Familiarity with arrays.
  3. Knowledge of simple algorithm concepts.

With these prerequisites, you will be able to grasp the concepts and code implementations discussed here.

1. Removing Duplicates from an Array

1.1 Naive Approach

Let’s start with a simple, naive approach to remove duplicates from an array.

C++
#include <iostream>

void removeDuplicates(int arr[], int& n) {
    int temp[n]; // Temporary array to store unique elements
    int j = 0;

    // Iterate through original array
    for (int i = 0; i < n; i++) {
        // Check if the element is already present in temp
        int k;
        for (k = 0; k < j; k++) {
            if (arr[i] == temp[k]) {
                break;
            }
        }
        // If element is not found in temp, add it
        if (k == j) {
            temp[j++] = arr[i];
        }
    }

    // Copy the unique elements back to the original array
    for (int i = 0; i < j; i++) {
        arr[i] = temp[i];
    }

    // Update the size of the array
    n = j;
}

int main() {
    int arr[] = {1, 2, 2, 3, 4, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    removeDuplicates(arr, n);

    std::cout << "Array after removing duplicates: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

1.2 Output Explanation

In this example, the input array is {1, 2, 2, 3, 4, 4, 5}. The program removes the duplicates and outputs:

C++
Array after removing duplicates: 1 2 3 4 5

1.3 Time Complexity

The time complexity of this naive approach is O(n2)O(n^2)O(n2) because for each element, we are checking all the previous elements to see if it is a duplicate.

2. Efficient Approach

2.1 Using Sorting

A more efficient way to remove duplicates is by first sorting the array and then removing adjacent duplicates.

C++
#include <iostream>
#include <algorithm>

void removeDuplicates(int arr[], int& n) {
    if (n == 0 || n == 1) return;

    // Sort the array
    std::sort(arr, arr + n);

    // Temporary array to store unique elements
    int temp[n];
    int j = 0;

    // Iterate through sorted array
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] != arr[i + 1]) {
            temp[j++] = arr[i];
        }
    }

    // Add the last element
    temp[j++] = arr[n - 1];

    // Copy the unique elements back to the original array
    for (int i = 0; i < j; i++) {
        arr[i] = temp[i];
    }

    // Update the size of the array
    n = j;
}

int main() {
    int arr[] = {1, 2, 2, 3, 4, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    removeDuplicates(arr, n);

    std::cout << "Array after removing duplicates: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

2.2 Output Explanation

The input array {1, 2, 2, 3, 4, 4, 5} is sorted and then duplicates are removed, resulting in:

C++
Array after removing duplicates: 1 2 3 4 5

2.3 Time Complexity

The time complexity of this approach is O(nlog⁡n)O(n \log n)O(nlogn) due to the sorting step, making it more efficient than the naive approach.

3. Using Hashing

3.1 Using an Unordered Set

Another efficient way is to use an unordered set to keep track of the unique elements.

C++
#include <iostream>
#include <unordered_set>

void removeDuplicates(int arr[], int& n) {
    std::unordered_set<int> set;
    int j = 0;

    for (int i = 0; i < n; i++) {
        // If element is not in the set, add it
        if (set.find(arr[i]) == set.end()) {
            set.insert(arr[i]);
            arr[j++] = arr[i];
        }
    }

    // Update the size of the array
    n = j;
}

int main() {
    int arr[] = {1, 2, 2, 3, 4, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    removeDuplicates(arr, n);

    std::cout << "Array after removing duplicates: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

3.2 Output Explanation

The input array {1, 2, 2, 3, 4, 4, 5} is processed using an unordered set to remove duplicates, resulting in:

C++
Array after removing duplicates: 1 2 3 4 5

3.3 Time Complexity

The time complexity of this approach is O(n) due to the use of a hash set for constant time complexity of insert and search operations.

Conclusion

A C++ program to remove duplicates from an array can be implemented using different approaches. The naive approach involves nested loops and has a time complexity of O(n^2). A more efficient approach involves sorting the array first and then removing adjacent duplicates, with a time complexity of O(nlogn). The most efficient approach uses hashing with an unordered set, achieving a time complexity of O(n)