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.

Table of Contents

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

- Initialize a variable count with zero which will count the number of distinct elements in the array.
- Run a loop for I in range 0 to n-1
- Declare a flag with false which is true if A[i] is a repeating element and vice versa
- Run a loop for j in range 0 to n-1
- If I is not equal j and A[i] is equal to A[j], assign flag=true and break

- If the flag is false, increment count by 1
- Check If count is equal to K, print A[i].

- 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

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

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