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