Minimum number of distinct elements present in a K-length subsequence in an array

0 0 6 minutes read

Given an array A[] consisting of N integers and an integer K, the task is to count the minimum number of distinct elements present in a subsequence of length K of the given array, A.

Examples:

Input: A = {3, 1, 3, 2, 3, 4, 5, 4}, K = 4
Output: 2
Explanation: The subsequence of length 4 containing minimum number of distinct elements is {3, 3, 3, 4}, consisting of 2 distinct elements, i.e. {3, 4}.

Input: A = {3, 1, 3, 2, 3, 4, 5, 4}, K = 5
Output: 2
Explanation: The subsequence of length 5 containing minimum number of distinct elements is {3, 3, 3, 4, 4}, consisting of 2 distinct elements, i.e. {3, 4}.

Naive Approach: The simplest approach is to generate all subsequences of length K and for each subsequence, find the number of distinct elements present in them. Finally, print the minimum number of distinct elements present.

Time Complexity: O(K * N^K)
Auxiliary Space: O(N)

Efficient Approach: The above approach can be optimized using Hashing. Follow the steps below to solve the problem:

Store the frequencies of all elements in the given array, A[] in a HashMap, say M.
Traverse the hashmap, M and push the frequencies in another array, say V.
Sort the array V in decreasing order.
Initialize two variables, cnt and len as 0, to store the required result and the length of the subsequence thus formed.
Traverse the array V[] using a variable, say i
- If the value of len ? K, then break out of the loop.
- Otherwise, increment the value of len by V[i] and cnt by 1.
After completing the above steps, print the value of cnt as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the minimum number
// of distinct elements present in any
// subsequence of length K of the given array
void findMinimumDistinct(int A[], int N, int K)
{
 
    // Stores the frequency
    // of each array element
    unordered_map<int, int> mp;
 
    // Traverse the array
    for (int i = 0; i < N; i++)
 
        // Update frequency
        // of array elements
        mp[A[i]]++;
 
    // Store the required result
    int count = 0;
 
    // Store the length of the
    // required subsequence
    int len = 0;
 
    // Store the frequencies
    // in decreasing order
    vector<int> counts;
 
    // Traverse the map
    for (auto i : mp)
 
        // Push the frequencies
        // into the HashMap
        counts.push_back(i.second);
 
    // Sort the array in decreasing order
    sort(counts.begin(), counts.end(),
         greater<int>());
 
    // Add the elements into the subsequence
    // starting from one with highest frequency
    for (int i = 0; i < counts.size(); i++) {
 
        // If length of subsequence is >= k
        if (len >= K)
            break;
        len += counts[i];
        count++;
    }
 
    // Print the result
    cout << count;
}
 
// Driver Code
int main()
{
    int A[] = { 3, 1, 3, 2, 3, 4, 5, 4 };
    int K = 4;
 
    // Store the size of the array
    int N = sizeof(A) / sizeof(A[0]);
 
    // Function Call to count minimum
    // number of distinct elements
    // present in a K-length subsequence
    findMinimumDistinct(A, N, K);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to count the minimum number
// of distinct elements present in any
// subsequence of length K of the given array
static void findMinimumDistinct(int A[], int N, int K)
{
     
    // Stores the frequency
    // of each array element
    Map<Integer, Integer> mp = new HashMap<>();
 
    // Traverse the array
    for(int i = 0; i < N; i++)
     
        // Update frequency
        // of array elements
        mp.put(A[i], mp.getOrDefault(A[i], 0) + 1);
 
    // Store the required result
    int count = 0;
 
    // Store the length of the
    // required subsequence
    int len = 0;
 
    // Store the frequencies
    // in decreasing order
    ArrayList<Integer> counts = new ArrayList<>();
 
    // Traverse the map
    for(Map.Entry<Integer, Integer> i : mp.entrySet())
     
        // Push the frequencies
        // into the HashMap
        counts.add(i.getValue());
 
    // Sort the array in decreasing order
    Collections.sort(counts, (a, b) -> b - a);
 
    // Add the elements into the subsequence
    // starting from one with highest frequency
    for(int i = 0; i < counts.size(); i++) 
    {
         
        // If length of subsequence is >= k
        if (len >= K)
            break;
             
        len += counts.get(i);
        count++;
    }
 
    // Print the result
    System.out.print(count);
}
 
// Driver code
public static void main(String[] args)
{
    int A[] = { 3, 1, 3, 2, 3, 4, 5, 4 };
    int K = 4;
 
    // Store the size of the array
    int N = A.length;
 
    // Function Call to count minimum
    // number of distinct elements
    // present in a K-length subsequence
    findMinimumDistinct(A, N, K);
}
}
 
// This code is contributed by offbeat

Python3

# Python3 program for the above approach
from collections import Counter
 
# Function to count the minimum number
# of distinct elements present in any
# subsequence of length K of the given array
def findMinimumDistinct(A, N, K):
     
    # Stores the frequency
    # of each array element
    mp = Counter(A)
     
    # Store the required result
    count = 0
     
    # Store the length of the
    # required subsequence
    length = 0
     
    # Store the frequencies
    # in decreasing order
    counts = []
     
    # Traverse the map
    for i in mp:
         
        # Push the frequencies
        # into the HashMap
        counts.append(mp[i])
         
    # Sort the array in decreasing order
    counts = sorted(counts)
    counts.reverse()
     
    # Add the elements into the subsequence
    # starting from one with highest frequency
    for i in range(len(counts)):
         
        # If length of subsequence is >= k
        if (length >= K):
            break
         
        length += counts[i]
        count += 1
         
    # Print the result
    print(count)
 
# Driver Code
A = [3, 1, 3, 2, 3, 4, 5, 4]
K = 4
 
# Store the size of the array
N = len(A)
 
# Function Call to count minimum
# number of distinct elements
# present in a K-length subsequence
findMinimumDistinct(A, N, K)
 
# This code is contributed by sudhanshugupta2019a

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class Program
{
  static void Main(string[] args)
  {
    int[] A = new int[] { 3, 1, 3, 2, 3, 4, 5, 4 };
    int K = 4;
    int N = A.Length;
 
    Console.WriteLine(FindMinimumDistinct(A, N, K));
  }
 
  static int FindMinimumDistinct(int[] A, int N, int K)
  {
    Dictionary<int, int> mp = new Dictionary<int, int>();
    foreach (var item in A)
    {
      if (mp.ContainsKey(item))
        mp[item]++;
      else
        mp[item] = 1;
    }
 
    int count = 0;
    int length = 0;
    List<int> counts = new List<int>();
    foreach (var item in mp)
      counts.Add(item.Value);
 
    counts.Sort();
    counts.Reverse();
 
    for (int i = 0; i < counts.Count; i++)
    {
      if (length >= K)
        break;
      length += counts[i];
      count++;
    }
 
    return count;
  }
}
 
// This code is contributed by shivamsharma215

Javascript

<script>
 
// JavaScript program for the above approach
 
 
// Function to count the minimum number
// of distinct elements present in any
// subsequence of length K of the given array
function findMinimumDistinct(A, N, K)
{
 
    // Stores the frequency
    // of each array element
    let mp = new Map();
 
    // Traverse the array
    for (let i = 0; i < N; i++){
 
        // Update frequency
        // of array elements
        if(mp.has(A[i])){
            mp.set(A[i],mp.get(A[i])+1)
        }
        else mp.set(A[i],1)
    }
 
    // Store the required result
    let count = 0;
 
    // Store the length of the
    // required subsequence
    let len = 0;
 
    // Store the frequencies
    // in decreasing order
    let counts = [];
 
    // Traverse the map
    for (let [i,j] of mp)
 
        // Push the frequencies
        // into the HashMap
        counts.push(j);
 
    // Sort the array in decreasing order
    counts.sort((a,b)=>b-a);
 
    // Add the elements into the subsequence
    // starting from one with highest frequency
    for (let i = 0; i < counts.length; i++) {
 
        // If length of subsequence is >= k
        if (len >= K)
            break;
        len += counts[i];
        count++;
    }
 
    // Print the result
    document.write(count);
}
 
// Driver Code
 
let A = [ 3, 1, 3, 2, 3, 4, 5, 4 ];
let K = 4;
 
// Store the size of the array
let N = A.length;
 
// Function Call to count minimum
// number of distinct elements
// present in a K-length subsequence
findMinimumDistinct(A, N, K);
 
// This code is contributed by shinjanpatra
</script>

Output:

Time Complexity: O(N*log(N))
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!