Print All Distinct Elements of a Given Integer Array

Difficulty Level Easy
Frequently asked in Amazon MakeMyTrip Zoho
Array Hash SortingViews 2217

Given an integer array, print all distinct elements in the array. The given array may contain duplicates and the output should print every element only once. The given array is not sorted.

Example

Input:

nums[]= {12, 10, 9, 45, 2, 10, 10, 45}

Output:

12, 10, 9, 45, 2

Approach 1: Brute force solution

Main idea

For every element, check if there is another element present or not whose value is the same and has an index less than the current index. If there is no such element, print the current element otherwise skip it.

Algorithm

  1. Run a loop for I in range 0 to n-1
    1. Run a loop for j in range 0 to i
      • If j==I, print nums[i].
      • If nums[i] is equal to nums[j], break out from this loop.
    2. Return.

Implementation for Print All Distinct Elements of a Given Integer Array

C++ program

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> nums(n);
    for(int i=0;i<n;i++)
    {
        cin>>nums[i];
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(j==i)
            {
                cout<<nums[j]<<" ";
            }
            if(nums[i]==nums[j])
            {
                break;
            }
        }
    }
    return 0;
}

5
3 3 1 2 1

3 1 2

JAVA program

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i=0;i<n;i++)
        {
            nums[i] = sc.nextInt();;
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<=i;j++)
            {
                if(j==i)
                {
                    System.out.print(nums[i]+" ");
                }
                if(nums[i]==nums[j])
                {
                    break;
                }
            }
        }
  }
}


10 
4 6 6 2 6 3 4 2 2 7
4 6 2 3 7

Complexity Analysis for Print All Distinct Elements of a Given Integer Array

Time complexity

We have two nested loops, each of size n. So the time complexity is O(N^2).

Space Complexity

We have not used any extra space so the time complexity is O(1).

Approach 2: Optimized solution with Hashing

Main idea

We will maintain a hash table which will store the elements we have already printed. So, we will iterate the array, if a found an element in the array which is not present in the hash table then we will print that element, and then we will insert it in the hash table, otherwise we will skip that element.

Algorithm

  1. Declare a hash table.
  2. Run a loop for I in range 0 to n-1:
    • If nums[i] is not present in the hash table, then print it and insert it in the hash table.
    • If nums[i] is not present in the hash table then skip it.
  3. Return.

For example, let’s say

nums[]={3, 3, 1, 2 ,1}

The table on the left side is our input array and orange color points to the current index.

The table on the right is the hash table.

Print All Distinct Elements of a Given Integer Array

Implementation for Print All Distinct Elements of a Given Integer Array

C++ program

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> nums(n);
    for(int i=0;i<n;i++)
    {
        cin>>nums[i];
    }
    unordered_set<int> hash_table;
    for(int i=0;i<n;i++)
    {
        if(hash_table.count(nums[i])==0)  //hash_table.count(x) returns 1 if x is present in the hash_table otherwise returns 0
        {
            hash_table.insert(nums[i]);
            cout<<nums[i]<<" ";
        }
    }
    return 0;
}

5
3 3 1 2 1

3 1 2

JAVA program

import java.util.*;
public class Main
{
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i=0;i<n;i++)
        {
            nums[i] = sc.nextInt();;
        }
        Set<Integer> hash_table = new HashSet<Integer>(); 
        for(int i=0;i<n;i++)
        {
            if(!hash_table.contains(nums[i]))  
            {
                hash_table.add(nums[i]);
                System.out.print(nums[i]+" ");
            }
        }
  }
}


10 
1 2 2 1 3 5 6 3 4 9
1 2 3 5 6 4 9

Complexity Analysis for Print All Distinct Elements of a Given Integer Array

Time complexity

We iterate the array only once and the time complexity of insert function in the unordered set is O(1), so total time complexity is O(N).

Space complexity

We took an extra hash table so our space complexity is O(N).

References

Translate »