Home » Technical Interview Questions » Array Interview Questions » Print All Distinct Elements of the Array

Print All Distinct Elements of the Array


Reading Time - 2 mins

We have an array of containing N integers which may be positive or negative. We have to print all distinct elements of the array. In other words, we can say that if a number occurs more than one time then we print only that number once.

Example

Input

8

2 3 1 2 3 5 4 -5

Output

2 3 1 5 4 -5

We can solve this question in so many ways and some of those approaches are used below. Please read patiently because every approach leads your knowledge.

 Approach 1 for Print All Distinct Elements of the Array

We can store the frequency of every element and print every number only once.

Algorithm

1. Simply Hash all the values and increase their count from 0 to the number of times they occur.

2. While printing we check if the count of that key is more than 0 and if yes we print it once.

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  unordered_map<int,int> m;
  for(int i=0;i<n;i++)
  {
      m[a[i]]++;
  }
  unordered_map<int,int> :: iterator i;
  for(i=m.begin();i!=m.end();i++)
  {
    cout<<i->first<<" ";  
  }
}
8
2 1 -2 3 4 3 2 1
4 3 -2 2 1

Complexity Analysis for Print All Distinct Elements of the Array

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

READ  Contiguous Array Leetcode

Space Complexity: O(N) because we use map to store the frequency of each elements.

Approach 2 for Print All Distinct Elements of the Array

When we use the SET data structure which containing elements in sorted order and each element present only once in the set. Below is the implementation using SET.

Algorithm

1. Use the SET data structure that stores unique keys and in a sorted manner.

2. Simply add all the elements and traverse the set using iterator.

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
  {
      cin>>arr[i];
  }
  set<int> S; // Set data structure stores unique element and  too sorted 
  
  for(int i=0;i<n;i++)
    S.insert(arr[i]);
    
  set<int> :: iterator it; //just traverse the set simply
  for(it = S.begin(); it != S.end(); it++)
    cout << *it << " ";
    
}
8
2 1 -2 3 4 3 2 1
-2 1 2 3 4

Complexity Analysis for Print All Distinct Elements of the Array

Time Complexity: O(NlogN) because insertion in SET takes logN time. So, here is the size of the array is N that’s why the time complexity in this nlogn.

Space Complexity: O(N) because we use SET for storing the elements. And the maximum size possible for SET is N.

Approach 3 for Print All Distinct Elements of the Array

Using sorting we can also print the distinct numbers.

Algorithm

1. Sort the array.

2. Traverse the array and skip similar adjacent elements.

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++)
  {
      cin>>arr[i];
  }
  sort(arr,arr+n); // sort the array so that similar elements will occur adjacent
  
  for(int i=0;i<n;)
  {
    cout << arr[i++] << " ";
    while(arr[i] == arr[i-1] and i < n)
      i++;
  }
    
}
8
3 2 1 5 3 2 1 -5
-5 1 2 3 5

Complexity Analysis

Time Complexity: O(NlogN) here we use sort function which has nlogn time complexity.

READ  Find The Duplicate Number

Space Complexity: O(1) because we don’t use any auxiliary space here.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions