Program to Remove Duplicate From Sorted Array in C++.

Given an integer array arr[] sorted in ascending order, the task is to remove duplicate elements such that the relative order of the elements should be kept the same.

Example:

Input: arr[] = {1, 1, 2, 2, 2, 3}
Output: arr[] = {1, 2, 3}

Input: arr[] = {1, 2, 5, 5}
Output: arr[] = {1, 2, 5}

There are multiple ways to solve this problem, let's discuss each of them one by one:

Approach 1: Brute Force Approach.

It is the simplest approach in which we are going to use extra space to store only unique elements. Below are the steps to follow:

Create a new array temp[].
Iterate through the original array arr[].
For each element, check if it is already present in the new array.
If not, add it to the new array.
The new array contains elements without duplicates.

At the end, you can copy the elements of the new array into the original array and return the original array.

Note: In the below code we have used std::vector() instead of the array because in real-world problems and in interviews we have to deal with vectors.

Example Code: Below is the C++ code implementation for the above approach.

//C++ code to remove duplicate elements from the array
#include <bits/stdc++.h>
using namespace std;

int removeDuplicatesBruteForce(vector<int>& arr) {
    vector<int> result;

    for (int i : arr) {
        //checking if element already exist
        if (find(result.begin(), result.end(), i) == result.end()) {
            result.push_back(i);
        }
    }
    arr = result;
    return result.size();
}

int main(){
    vector<int> arr = {1, 1, 2, 2, 2, 3, 5};

    int n = removeDuplicatesBruteForce(arr);

    for(int i = 0; i < n; i++){
        cout << arr[i] <<" ";
    }

    return 0;
}

Output:

1 2 3 5

Time Complexity: O(n^2) where n is the number of elements in the array.

Space Complexity: O(n) where n is the number of elements in the array.

Approach 2: Optimized Approach.

In this approach, we are going to iterate the complete array only once to find all unique elements. Below are the steps to be followed:

Create a result vector and add the first element of the array.
Iterate through the original array from the second element.
For each element, check if it is equal to the previous element.
If not, add it to the result vector.
The result vector will now contain elements without duplicates.

Example Code: Below is the C++ code implementation for the above approach.

//C++ code to remove duplicate elements from the array
#include <bits/stdc++.h>
using namespace std;

int removeDuplicatesOptimized(vector<int>& arr) {
    vector<int> result;

    if (!arr.empty()) {
        //add first element to array
        result.push_back(arr[0]);

        for (size_t i = 1; i < arr.size(); ++i) {
            //check if element is equal to previous element
            if (arr[i] != arr[i - 1]) {
                result.push_back(arr[i]);
            }
        }
    }
    //copy unique elements to original array
    arr = result;
    return result.size();
}

int main(){
    vector<int> arr = {1, 1, 2, 2, 2, 2, 5};

    int n = removeDuplicatesOptimized(arr);

    for(int i = 0; i < n; i++){
        cout << arr[i] <<" ";
    }

    return 0;
}

Output:

1 2 5

Time Complexity: O(n) where n is the number of elements in the array.

Space Complexity: O(n) where n is the number of elements in the array.

Approach 3: Two Pointer Approach.

In this approach, we are not going to use any extra space to solve the problem instead we are going to use an in-place approach. Below are the steps to follow:

Use two pointers - one to iterate through the array and another to keep track of the position to overwrite.
Iterate through the array from the second element.
If the current element is different from the previous one, overwrite the next position with the current element.
The array up to the position of the second pointer will now contain elements without duplicates.

By completing the above steps all unique elements will move from the given vector (array) and then you can resize the vector up to the last overwrite position.

Note: We are starting the iteration from 1 because the element at position 0 is always unique and it does not require any replacement.

Example Code: Below is the C++ code implementation for the above approach.

//C++ code to remove duplicate elements from the array
//In-place approach
#include <bits/stdc++.h>
using namespace std;

int removeDuplicatesInPlace(vector<int>& arr) {

    int writeIndex = 1; // Position to overwrite

    for (size_t i = 1; i < arr.size(); ++i) {
        if (arr[i] != arr[i - 1]) {
            arr[writeIndex++] = arr[i];
        }
    }

    // Resize the array to the size of unique elements
    arr.resize(writeIndex);
    return arr.size();
}

int main(){
    vector<int> arr = {0, 1, 1, 2, 2, 2, 2, 4, 5, 5};

    int n = removeDuplicatesInPlace(arr);

    for(int i = 0; i < n; i++){
        cout << arr[i] <<" ";
    }

    return 0;
}

Output:

0 1 2 4 5

Time Complexity: O(n) where n is the number of elements in the array.

Space Complexity: O(1) in-place modification is performed so no extra space is required.

So these are the three different approaches to removing duplicate elements from a sorted array.

Program to Remove Duplicate From Sorted Array in C++.

Approach 1: Brute Force Approach.

Approach 2: Optimized Approach.

Approach 3: Two Pointer Approach.

No comments:

Post a Comment