# K-th Distinct Element in an Array  Difficulty Level Medium
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

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
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.

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, ### 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).