# K-th Distinct Element in an Array

Difficulty Level Medium
Divide and Conquer HeapViews 1557

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

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

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

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

Translate »