K-th Distinct Element in an Array  

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple ByteDance eBay Expedia Facebook Google LinkedIn Microsoft Oracle Salesforce Spotify Walmart Labs
Divide and Conquer Heap

You are given an integer array A, print k-th distinct element in an array. The given array may contain duplicates and the output should print k-th distinct element among all unique elements in an array. If k is more than a number of distinct elements, then report it.

Example  

Input:

A[]={3,4,4,1,2,3}

K=2

Please click Like if you loved this article?

Output:

K-th non-repeating element is 2.

Explanation:

First nonrepeating element is 1,

Second non-repeating element is 2.

Approach 1: Brute force  

Main idea

We will maintain a count variable that will store the number of non-repeating elements we have found. Now we will iterate over all the elements and for each element, we will iterate over the array to check if this is a non-repeating element or not, if it is then we will increment the count by 1. The element for which count becomes equal to K, we will print that element.

Algorithm for K-th Distinct Element in an Array

  1. Initialize a variable count with zero which will count the number of distinct elements in the array.
  2. Run a loop for I in range 0 to n-1
    1. Declare a flag with false which is true if A[i] is a repeating element and vice versa
    2. Run a loop for j in range 0 to n-1
      1. If I is not equal j and A[i] is equal to A[j], assign flag=true and break
    3. If the flag is false, increment count by 1
    4. Check If count is equal to K, print A[i].
  3. Return
See also
Print Fibonacci sequence using 2 variables

Implementation

C++ program

#include <bits/stdc++.h>
using namespace std;
void kthDistinctElement(vector<int> &A, int k)
{
    int n = A.size();
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        bool flag = false;
        for (int j = 0; j < n; j++)
        {
            if (i != j and A[i] == A[j])
            {
                flag = true;
                break;
            }
        }
        if (!flag)
        {
            count++;
        }
        if (count == k)
        {
            cout << "K-th non-repeating element is: " << A[i] << endl;
            return;
        }
    }
    cout << "K is greater than number of distinct element in the array." << endl;
    return;
}
int main()
{
    vector<int> A = {3, 4, 4, 1, 2, 3};
    int k = 2;
    kthDistinctElement(A, k);
    return 0;
}
K-th non-repeating element is: 2

JAVA program

public class Main
{
    static void kthDistinctElement(int A[], int k)
    {
        int n=A.length;
        int count = 0;
        for (int i = 0; i < n; i++)
        {
            boolean flag = false;
            for (int j = 0; j < n; j++)
            {
                if (i != j && A[i] == A[j])
                {
                    flag = true;
                    break;
                }
            }
            if (!flag)
            {
                count++;
            }
            if (count == k)
            {
                System.out.println("K-th non-repeating element is: " + A[i]);
                return;
            }
        }
        System.out.println("K is greater than number of distinct element in the array.");
    }
  public static void main(String[] args) {
    int A[] = {3, 4, 4, 1, 2, 3};
        int k = 2;
        kthDistinctElement(A, k);
  }
}
K-th non-repeating element is: 2

Complexity Analysis for K-th Distinct Element in an Array

Time complexity

We are using two nested loops, both of size N. So, the total time complexity is O(N^2).

Space complexity

We are not using any extra space, so the space complexity is O(1).

Approach 2: Using hashing  

Main idea

We will store the frequency of each element of the array in a hash table. Now we will maintain a count variable that will store the number of non-repeating elements we have found. Next, we will iterate over all the elements, and for each element, we will check if its frequency is greater than 1 or not, if it is equal to 1, then we will increment the count by 1. The element for which count becomes equal to K, we will print that element.

See also
Implementation of Deque using circular array

Algorithm for K-th Distinct Element in an Array

  1. Declare a hash table which will store the frequency of each element of the array.
  2. Initialize a variable count with zero which will count the number of distinct elements in the array.
  3. Run a loop for I in range 0 to n-1
    1. If the frequency of A[i] is 1, increment count by 1.
    2. If count is equal to K, print A[i].
  4. Return

For example:

A[]={3,4,4,1,2,3}

K=2

The hash table will look like this,

K-th Distinct Element in an ArrayPin

Implementation

C++ program

#include <bits/stdc++.h>
using namespace std;
void kthDistinctElement(vector<int> &A, int k)
{
    int n = A.size();
    int count = 0;
    unordered_map<int, int> hash_table;
    for (int i = 0; i < n; i++)
    {
        hash_table[A[i]]++;
    }
    for (int i = 0; i < n; i++)
    {
        if (hash_table[A[i]] == 1)
        {
            count++;
        }
        if (count == k)
        {
            cout << "K-th non-repeating element is: " << A[i] << endl;
            return;
        }
    }
    cout << "K is greater than number of distinct element in the array." << endl;
    return;
}
int main()
{
    vector<int> A = {3, 4, 4, 1, 2, 3};
    int k = 2;
    kthDistinctElement(A, k);
    return 0;
}
K-th non-repeating element is: 2

JAVA program

import java.util.*; 
public class Main
{
    static void kthDistinctElement(int A[], int k)
    {
        int n=A.length;
        int count = 0;
        HashMap <Integer, Integer> hash_table = new HashMap<Integer, Integer> ();  
        for (int i = 0; i < n; i++)  
        { 
            if(hash_table.containsKey(A[i])) 
                hash_table.put(A[i], hash_table.get(A[i]) + 1); 
            else
                hash_table.put(A[i], 1); 
        } 
        for (int i = 0; i < n; i++)
        {
            if (hash_table.get(A[i])==1)
            {
                count++;
            }
            if (count == k)
            {
                System.out.println("K-th non-repeating element is: " + A[i]);
                return;
            }
        }
        System.out.println("K is greater than number of distinct element in the array.");
    }
  public static void main(String[] args) {
    int A[] = {3, 4, 4, 1, 2, 3};
        int k = 2;
        kthDistinctElement(A, k);
  }
}
K-th non-repeating element is: 2

Complexity Analysis for K-th Distinct Element in an Array

Time complexity

We are iterating over the array only twice. So, the total time complexity is O(N).

Please click Like if you loved this article?

See also
Find any one of the multiple repeating elements in read only array

Space complexity

We are maintaining a hash table to store the frequency of elements in the array. So, the space complexity is O(N).

References

Please click Like if you loved this article?