Given three integers N, X, Y, and an array arr[] of size N, the task is to find the count of subarrays having at least X distinct elements that occur only Y times.
Example:
Input: N = 9, X = 2, Y = 2, arr[] = {2, 1, 2, 5, 3, 1, 3, 2, 5}
Output:10
Explanation:
Subarrays with at least X distinct elements occurring exactly Y times are:
{2, 1, 2, 5, 3, 1}, {2, 1, 2, 5, 3, 1, 3}, {2, 1, 2, 5, 3, 1, 3, 2}, {2, 1, 2, 5, 3, 1, 3, 2, 5},
{1, 2, 5, 3, 1, 3}, {1, 2, 5, 3, 1, 3, 2}, {1, 2, 5, 3, 1, 3, 2, 5}, {2, 5, 3, 1, 3, 2},
{2, 5, 3, 1, 3, 2, 5}, {5, 3, 1, 3, 2, 5}Input: N = 3, X = 1, Y = 2, arr[] = {1, 3, 5}
Output: 0
Explanation: No element is occurring twice in the given array
Naive Approach: The idea is to generate all possible subarrays of the given array and traverse over the generated subarrays to find the frequency of all distinct elements. Then check whether there are at least X distinct elements that occur only Y times in the subarray. If found, increment the result and return the final result.
Time Complexity: O(N3)
Auxiliary Space: O(N)
Efficient Approach: The problem can also be solved in an efficient way based on the following idea:
Keep track of the frequency of elements while generating the subarray and count of unique elements with exactly Y occurrences in that subarray with the help of hashing. In this way, there is no need to build all the subarrays and check them afterward.
Follow the steps below to implement the above idea:
- Iterate from i = 0 to N – 1:
- Declare a hash map (say cntFreq) to store the frequency of the distinct elements in the subarray.
- Initialize a variable (say cntDistinct) to store the number of distinct elements that occur exactly Y times in the subarray.
- Iterate using a nested loop from j = i to N to consider all the subarrays:
- Increment the frequency of arr[j].
- If the frequency is Y then increment cntDistinct.
- If frequency exceeds Y and becomes Y+1, decrement cntDistinct,
- If the subarray has at least X distinct elements satisfying the condition then increase the count of subarrays fulfilling the condition.
- Finally, return the count of the subarrays.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to count the number of subarraysint countSubarray(int arr[], int X, int Y, int N){ // To store the total number of subarrays // that satisfy the condition. int cntSub = 0; for (int i = 0; i < N; i++) { int cntDistinct = 0; // To store frequency of distinct elements unordered_map<int, int> cntFreq; for (int j = i; j < N; j++) { // Increment the frequency of // current element in map cntFreq[arr[j]]++; if (cntFreq[arr[j]] == Y) { cntDistinct++; } else if (cntFreq[arr[j]] == Y + 1) { // Decrement if current element's // frequency equal Y+1 because the // cntDistinct is incremented at Y. cntDistinct--; } // Increment cntSub if // cntDistinct >= X if (cntDistinct >= X) { cntSub++; } } } // Print count of subarrays return cntSub;}// Driver Codeint main(){ int N = 9, X = 2, Y = 2; int arr[] = { 2, 1, 2, 5, 3, 1, 3, 2, 5 }; // Function call cout << countSubarray(arr, X, Y, N); return 0;} |
Java
// Java code to implement the approachimport java.util.TreeMap;class GFG { // Function to count the number of subarrays static int countSubarray(int arr[], int X, int Y, int N) { // To store the total number of subarrays // that satisfy the condition. int cntSub = 0; for (int i = 0; i < N; i++) { int cntDistinct = 0; // To store frequency of distinct elements TreeMap<Integer, Integer> cntFreq = new TreeMap<Integer, Integer>(); for (int j = i; j < N; j++) { // Increment the frequency of // current element in map if (cntFreq.containsKey(arr[j])) { cntFreq.put(arr[j], cntFreq.get(arr[j]) + 1); } else { cntFreq.put(arr[j], 1); } if (cntFreq.get(arr[j]) == Y) { cntDistinct++; } else if (cntFreq.get(arr[j]) == Y + 1) { // Decrement if current element's // frequency equal Y+1 because the // cntDistinct is incremented at Y. cntDistinct--; } // Increment cntSub if // cntDistinct >= X if (cntDistinct >= X) { cntSub++; } } } // Print count of subarrays return cntSub; } // Driver Code public static void main(String args[]) { int N = 9, X = 2, Y = 2; int arr[] = { 2, 1, 2, 5, 3, 1, 3, 2, 5 }; // Function call System.out.println(countSubarray(arr, X, Y, N)); }}// This code is contributed by gfgking. |
Python3
# Python3 code to implement the approach# Function to count the number of subarraysdef countSubarray(arr, X, Y, N) : # To store the total number of subarrays # that satisfy the condition. cntSub = 0; for i in range(N) : cntDistinct = 0; # To store frequency of distinct elements cntFreq = dict.fromkeys(arr,0); for j in range(i, N) : # Increment the frequency of # current element in map cntFreq[arr[j]] += 1; if (cntFreq[arr[j]] == Y) : cntDistinct += 1; elif (cntFreq[arr[j]] == Y + 1) : # Decrement if current element's # frequency equal Y+1 because the # cntDistinct is incremented at Y. cntDistinct -= 1; # Increment cntSub if # cntDistinct >= X if (cntDistinct >= X) : cntSub += 1; # Print count of subarrays return cntSub;# Driver Codeif __name__ == "__main__" : N = 9; X = 2; Y = 2; arr = [ 2, 1, 2, 5, 3, 1, 3, 2, 5 ]; # Function call print(countSubarray(arr, X, Y, N)); # This code is contributed by AnkThon |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class GFG { // Function to count the number of subarrays static int countSubarray(int []arr, int X, int Y, int N) { // To store the total number of subarrays // that satisfy the condition. int cntSub = 0; for (int i = 0; i < N; i++) { int cntDistinct = 0; // To store frequency of distinct elements Dictionary<int, int> cntFreq = new Dictionary<int, int>(); for (int j = i; j < N; j++) { // Increment the frequency of // current element in map if (cntFreq.ContainsKey(arr[j])) { cntFreq[arr[j]] = cntFreq[arr[j]] + 1; } else { cntFreq.Add(arr[j], 1); } if (cntFreq[arr[j]] == Y) { cntDistinct++; } else if (cntFreq[arr[j]] == Y + 1) { // Decrement if current element's // frequency equal Y+1 because the // cntDistinct is incremented at Y. cntDistinct--; } // Increment cntSub if // cntDistinct >= X if (cntDistinct >= X) { cntSub++; } } } // Print count of subarrays return cntSub; } // Driver Code public static void Main(string []args) { int N = 9, X = 2, Y = 2; int []arr = { 2, 1, 2, 5, 3, 1, 3, 2, 5 }; // Function call Console.WriteLine(countSubarray(arr, X, Y, N)); }}// This code is contributed by AnkThon |
Javascript
<script> // Javascript program to Count subarrays having // at least X distinct elements that occur exactly Y times // Function to count the number of subarrays function countSubarray(arr, X, Y, N){ // To store the total number of subarrays // that satisfy the condition. var cntSub = 0; for (var i = 0; i < N; i++) { var cntDistinct = 0; // To store frequency of distinct elements const cntFreq = new Map(); for (var j = i; j < N; j++) { // Increment the frequency of // current element in map if (cntFreq.has(arr[j])) { cntFreq.set(arr[j], cntFreq.get(arr[j]) + 1); } else { cntFreq.set(arr[j], 1); } if (cntFreq.get(arr[j]) == Y) { cntDistinct++; } else if (cntFreq.get(arr[j]) == Y + 1) { // Decrement if current element's // frequency equal Y+1 because the // cntDistinct is incremented at Y. cntDistinct--; } // Increment cntSub if // cntDistinct >= X if (cntDistinct >= X) { cntSub++; } } } // Print count of subarrays return cntSub; } // Driver Code var N = 9, X = 2, Y = 2; var arr = [2, 1, 2, 5, 3, 1, 3, 2, 5]; // Function call document.write(countSubarray(arr, X, Y, N)); //This code is contributed by shruti456rawal</script> |
Output
10
Time Complexity: O(N2)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
