Arrays: Given an array, and value K find the k th distinct element among unique elements in an array

Problem Statement:

You are given an array and a value “k”.

The array may have duplicates and the output should print the k-th element among all unique element.

Example:

Input: arr[] = {1, 2, 1, 3, 5, 2}, k = 2
Output: 5

The first non repeating element is 3 and second non repeating element is 5

Solution 1: Brute force approach

You need to take 2 nested loops.

Outer loop will run from left to right.

Inner loop checks if the picked element is present.

If not present, increment the distinct element count and return when the count becomes k.

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

Solution 2: Hashing Approach

Store the element with the count of occurrence.

Then traverse the hash table again to find the element with count equal to 1 and then increment the K value and return the current element.

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

Code Solution

#include <iostream>
#include <vector>
#include <stack>
#include <bits/stdc++.h>

using namespace std;

int solution_1(vector<int> arr, int k)
{
    int dist_count = 0;
    int n = arr.size();
    for (int i = 0; i < n; i++)
    {

        int j;
        for (j = 0; j < n; j++)
            if (i != j && arr[j] == arr[i])
                break;

        // If unique element
        if (j == n)
            dist_count++;

        if (dist_count == k)
            return arr[i];
    }

    return -1;
}

int solution_2(vector<int> arr, int k)
{ 

    int n = arr.size(); 
    
    unordered_map<int, int> h;
    
    for (int i = 0; i < n; i++)
        h[arr[i]]++;

    if (h.size() < k)
        return -1;


    int dist_count = 0;
    
    for (int i = 0; i < n; i++)
    {
        if (h[arr[i]] == 1)
            dist_count++;
            
        if (dist_count == k)
            return arr[i];
    }

    return -1;
}
int main ()
{
    vector<int> arr = {1, 2, 1, 3, 5, 2};
    int k = 2;
    cout << solution_1(arr, k);
    cout << solution_2(arr, k);
    return 0;
}

Output

5
5