Hashing: You are given an array, you need to return kth distinct element

Problem Statement:

You are given an array with duplicate elements and a k integer.

You need to find the k’th non repeating integer in the array.

Example:

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

Output: 4

First non repeating element is 2, second non-repeating element is 4. Hence the output is 4.

Solution 1: Brute force approach

In this solution, we will use 2 nested loops.

Outer loop will pick the elements from left to right.

Inner loop will check if the element of the outer loop is present in the loop.

If the element is unique, then increment the count, once the count reach the k, then print the element.

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

Solution 2: Hashing Approach

We will traverse the array and store the element in hash table with their occurrence.

Then traverse the array again find the elements whose count 1 and if the count becomes k, return the current element.

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

Code Solution

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
using namespace std;


int solution_1 (vector<int> arr, int k)
{
    int dist_count = 0;
    int len = arr.size();

    for (int i = 0; i < len; i++)
    {
        int j; //check if current element is present in the array
        for (j = 0; j < len; j++)
            if (i != j && arr[j] == arr[i])
                break; //if yes, break

        // the element is unique
        if (j == len)
            dist_count++;

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

    return -1;
}


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

    int len = arr.size(); 

    unordered_map<int, int> hash_table;
    
    //map the element with occurance
    for (int i = 0; i < len; i++)
        hash_table[arr[i]]++;

    // condition to check
    // if hash_table is less than k
    if (hash_table.size() < k)
        return -1;

    //check for distinct count
    int dist_count = 0;
    for (int i = 0; i < len; i++)
    {
        if (hash_table[arr[i]] == 1)
            dist_count++;
        if (dist_count == k)
            return arr[i];
    }

    return -1;
}

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

Output

4
4