Remove Duplicates From an Unsorted Array

Problem Statement: Given an unsorted array, remove duplicates from the array.

Examples:

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

Explanation: Removed all the duplicate elements

Example 2:
Input: arr[]={4,3,9,2,4,1,10,89,34}
Output: {3,4,9,2,1,10,34,89}
Explanation: Removed all the duplicate elements

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1: Brute Force Approach

Intuition:

-> We can use an array to store non-duplicate and will return this array

-> This array will be a boolean array. Corresponding to each index, true means element is Unique else it’s duplicate.

Approach:

-> We will place true from i to n-1 in the mark array

-> We will use a nested loop. In the outer loop, we will iterate the given array. Let the current number be ‘x’. Now in the inner loop, we will iterate from the given ‘x’ to the end of the array.

-> If we find ‘x’, we will mark x as false

-> Same can be done throughout for each element of the array

Code:

C++ Code

#include <bits/stdc++.h>

using namespace std;

class removeDuplicate {

  public:

    void duplicate(int arr[], int n) {
      int mark[n] = {
        1
      };
      for (int i = 0; i < n; i++) {

        if (mark[i] == 1) {

          for (int j = i + 1; j < n; j++) {

            if (arr[i] == arr[j]) {

              mark[j] = 0;
            }
          }
        }
      }

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

};
int main() {

  int arr[] = {4, 3, 9, 2, 4, 1, 10, 89, 34} ;
  int n = 9;

  removeDuplicate d1;
  d1.duplicate(arr, n);

  return 0;
}

Output: 3,9,2,4,1,10,89,34,

Time complexity : O(n*n) + O(n)

-> O(n*n) for updating boolean array

-> O(n) for the printing of non-duplicates

Space complexity: O(n) + O(n)

-> O(n) marking array

-> O(n) answer array

Java Code

import java.util.*;

public class Solution {

  static void duplicate(int arr[], int n) {

    int mark[] = new int[n];

    for (int i = 0; i < n; i++) {
      mark[i] = 1;
    }

    for (int i = 0; i < n; i++) {
      if (mark[i] == 1) {
        for (int j = i + 1; j < n; j++) {
          if (arr[i] == arr[j]) {
            mark[j] = 0;
          }
        }
      }
    }

    for (int i = 0; i < n; i++) {
      if (mark[i] == 1) {
        System.out.print(arr[i] + ",");
      }
    }
  }

  public static void main(String[] args) {
    int n = 9;
    int arr[] = { 4, 3, 9, 2, 4, 1, 10, 89, 34 };

    duplicate(arr, n);
  }
}

Output: 3,9,2,4,1,10,89,34,

Time complexity : O(n*n) + O(n)

-> O(n*n) for updating boolean array

-> O(n) for the printing of non-duplicates

Space complexity: O(n) + O(n)

-> O(n) marking array

-> O(n) answer array

Solution 2: Hashtable Method

Intuition:

-> We can use Hashtable ( map in C++, HashMap in Java) to check duplicate elements of the array.

-> In Hashtable, insertion and searching in O(1) average.

Approach:

-> We will create a hash table of size n and store elements in it. Before inserting a new element in the hash table, if it already exists in the hash table.

-> If the current element is not present we will print it else will move on.

Code:

C++ Code

#include <bits/stdc++.h>
using namespace std ;

class removeDuplicate {

public:

    void duplicate(int arr[], int n) {

        map<int, int>mp ;

        for (int i = 0; i < n; i++) {
            if (mp.find(arr[i]) == mp.end()) {
                cout << arr[i] << " ";
                mp[arr[i]]++;
            }
        }
    }

} ;
int main() {

    int arr[] = {4, 3, 9, 2, 4, 1, 10, 89, 34} ;
    int n = 9  ;

    removeDuplicate d1  ;
    d1.duplicate(arr, n) ;

    return 0 ;
}

Output: 4 3 9 2 1 10 89 34

Time Complexity: O(n) + O(n) = O(n)

Reason:Iteration in array , searching hash table

Space Complexity : O(n)

Reason : Using hashing