K-th Distinct Element in an Array

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple ByteDance eBay Expedia Facebook Google LinkedIn Microsoft Oracle Salesforce Spotify Walmart Labs
Divide and Conquer HeapViews 2242

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.

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

  1. Initialize a variable count with zero which will count the number of distinct elements in the array.
  2. Run a loop for I in range 0 to n-1
    1. Declare a flag with false which is true if A[i] is a repeating element and vice versa
    2. Run a loop for j in range 0 to n-1
      1. If I is not equal j and A[i] is equal to A[j], assign flag=true and break
    3. If the flag is false, increment count by 1
    4. Check If count is equal to K, print A[i].
  3. 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

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

For example:

A[]={3,4,4,1,2,3}

K=2

The hash table will look like this,

K-th Distinct Element in an Array

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

References

Translate ยป