k-th distinct (non-repeating) element in an Array

Given an integer array arr[] a non negative integer k, 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 elements in the array. If k is more than number of distinct elements, print -1.

Examples :

Input : arr[] = {1, 2, 1, 3, 4, 2}, k = 2
Output : 2
Explanation:
First non-repeating element is 1.
Second non-repeating element is 2.

Input : arr[] = {1, 2, 50, 10, 20, 2},  k = 3
Output : 50
Explanation:
First non-repeating element is 1
Second non-repeating element is 2
Third non-repeating element is 50

Input : {2, 2, 2, 2}, k = 2
Output : -1
Explanation:
First non-repeating element is 2.
Second and consecutive non-repeating element does not exist. 

Naive Approach: A simple solution is to use two nested loops where outer loop picks elements from left to right, and inner loop checks if the picked element is present somewhere else and makes it INT_MIN. If i-th element is not INT_MIN, then increment distinct. If distinct becomes k, return current element.

#include <bits/stdc++.h>
using namespace std;

int printKDistinct(int arr[],int& n,int& k)
{
    int distinct=0,i,j;
    
    if(k<=0)
    return -1;
    
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(arr[i]==arr[j])
            arr[j]=INT_MIN;
        }
        if(arr[i]!=INT_MIN)
        distinct++;
        if(distinct==k)
        return arr[i];
    }
    return -1;
}

int main()
{
    int ar[] =  {1, 2, 1, 3, 4, 2};
    int n = sizeof(ar) / sizeof(ar[0]);
    int k = 2;
    cout << printKDistinct(ar, n, k);
    return 0;
}

Time Complexity: O(n^2)
Auxiliary Space: O(1)

Efficient Approach:
Using STL Sets: An Efficient approach is to use Sets to store elements by traversing the given array and check its size at each iteration. If its size becomes equal to k then return the current element. Otherwise, k is greater than the number of distinct values present in the array so return -1.

#include <bits/stdc++.h>
using namespace std;

int printKDistinct(int arr[],int& n,int& k)
{
    set<int>unique;
    for(int i=0;i<n;i++)
    {
        unique.insert(arr[i]);
        if(unique.size()==k)
        return arr[i];
    }
    return -1;
}

int main()
{
    int arr[] = {1, 2, 50, 10, 20, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << printKDistinct(arr, n, k);
    return 0;
}

Time Complexity: O(n log n) because insertion in Sets takes log n time due to sorting property.
Auxiliary Space: O(n)

Using Hash-Map: An efficient solution is to use Hashing to solve this in O(n) time in worst case.

1. Create an empty hash table.
2. Traverse input array from left to right and check whether current element is present in the map or not.
3. If it is not present increment distinct.
4. If distinct becomes k, return current element.
5. If k is greater than the number of distinct elements present in the array then return -1.

#include <bits/stdc++.h>
using namespace std;

int printKDistinct(int arr[],int& n,int&k)
{
    int distinct=0;
    unordered_map<int,bool>freq;
    
    for(int i=0;i<n;i++){
        if(!freq[arr[i]])
        distinct++;
    freq[arr[i]]=1;
    if(distinct==k)
    return arr[i];
    }
    return -1;
}

int main()
{
    int arr[] = {2,2,2,2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << printKDistinct(arr, n, k);
    return 0;
}

Time Complexity: O(n)
Auxiliary Space: O(n)