Count subarrays having total distinct elements same as original array
Given an array of n integers. Count the total number of sub-arrays having total distinct elements, the same as that of the total distinct elements of the original array.
Examples:
Input : arr[] = {2, 1, 3, 2, 3} Output : 5 Total distinct elements in array is 3 Total sub-arrays that satisfy the condition are: Subarray from index 0 to 2 Subarray from index 0 to 3 Subarray from index 0 to 4 Subarray from index 1 to 3 Subarray from index 1 to 4 Input : arr[] = {2, 4, 5, 2, 1} Output : 2 Input : arr[] = {2, 4, 4, 2, 4} Output : 9
A Naive approach is to run a loop one inside another and consider all sub-arrays and, for every sub-array, count all distinct elements by using hashing and compare them with the total distinct elements of the original array.
- Initialise an unordered set unst1 to count distinct elements.
- Initialise a variable totalDist for total number of distinct elements in given array.
- Generate all the subarray and for every element count the distinct element in that subarray.
- Check if the number of distinct elements of the current subarray is equal to totalDist then increment the count by 1.
- Finally, return count.
Below is the implementation of the above approach:
C++
// C++ program Count total number of sub-arrays // having total distinct elements same as that // original array. #include <bits/stdc++.h> using namespace std; // Function to calculate distinct sub-array int countDistictSubarray( int arr[], int n) { unordered_set< int > unst1; for ( int i = 0; i < n; i++) unst1.insert(arr[i]); int totalDist = unst1.size(); int count = 0; for ( int i = 0; i < n; i++) { unordered_set< int > unst; for ( int j = i; j < n; j++) { unst.insert(arr[j]); if (unst.size() == totalDist) count++; } } return count; } // Driver code int main() { int arr[] = { 2, 1, 3, 2, 3 }; int n = sizeof (arr) / sizeof (arr[0]); cout << countDistictSubarray(arr, n) << endl; return 0; } // This code is contributed by hkdass001 |
Java
import java.util.*; // Function to calculate distinct sub-array public class Gfg { public static int countDistictSubarray( int [] arr, int n) { Set<Integer> unst1 = new HashSet<>(); for ( int i = 0 ; i < n; i++) unst1.add(arr[i]); int totalDist = unst1.size(); int count = 0 ; for ( int i = 0 ; i < n; i++) { Set<Integer> unst = new HashSet<>(); for ( int j = i; j < n; j++) { unst.add(arr[j]); if (unst.size() == totalDist) count++; } } return count; } // Driver code public static void main(String[] args) { int [] arr = { 2 , 1 , 3 , 2 , 3 }; int n = arr.length; System.out.println(countDistictSubarray(arr, n)); } } |
Python3
# Python3 program to count total number of sub-arrays # having total distinct elements same as that # original array. # Function to calculate distinct sub-array def countDistictSubarray(arr, n): unst1 = set (arr) totalDist = len (unst1) count = 0 for i in range (n): unst = set () for j in range (i, n): unst.add(arr[j]) if len (unst) = = totalDist: count + = 1 return count # Driver code arr = [ 2 , 1 , 3 , 2 , 3 ] n = len (arr) print (countDistictSubarray(arr, n)) # This code is contributed by Prajwal Kandekar |
C#
using System; using System.Collections.Generic; class Gfg { public static int countDistictSubarray( int [] arr, int n) { HashSet< int > unst1 = new HashSet< int >(); for ( int i = 0; i < n; i++) unst1.Add(arr[i]); int totalDist = unst1.Count; int count = 0; for ( int i = 0; i < n; i++) { HashSet< int > unst = new HashSet< int >(); for ( int j = i; j < n; j++) { unst.Add(arr[j]); if (unst.Count == totalDist) count++; } } return count; } // Driver code public static void Main( string [] args) { int [] arr = { 2, 1, 3, 2, 3 }; int n = arr.Length; Console.WriteLine(countDistictSubarray(arr, n)); } } // This code is contributed by divya_p123. |
Javascript
// Javascript program Count total number of sub-arrays // having total distinct elements same as that // original array. // Function to calculate distinct sub-array function countDistinctSubarray(arr, n) { const unst1 = new Set(arr); const totalDist = unst1.size; let count = 0; for (let i = 0; i < n; i++) { const unst = new Set(); for (let j = i; j < n; j++) { unst.add(arr[j]); if (unst.size === totalDist) { count += 1; } } } return count; } // Driver code const arr = [2, 1, 3, 2, 3]; const n = arr.length; console.log(countDistinctSubarray(arr, n)); |
Output
5
Time Complexity: O(n*n)
Auxiliary Space: O(n)
An efficient approach is to use a sliding window to count all distinct elements in one iteration.
- Find the number of distinct elements in the entire array. Let this number be k <= N. Initialize Left = 0, Right = 0 and window = 0.
- Increment right until the number of distinct elements in the range [Left=0, Right] is equal to k(or window size would not equal to k), let this right be R1. Now, since the sub-array [Left = 0, R1] has k distinct elements, so all the sub-arrays starting at Left = 0 and ending after R1 will also have k distinct elements. Thus, add N-R1+1 to the answer because [Left.. R1], [Left.. R1+1], [Left.. R1+2] … [Left.. N-1] contains all the distinct numbers.
- Now keeping R1 same, increment left. Decrease the frequency of the previous element i.e., arr[0], and if its frequency becomes 0, decrease the window size. Now, the sub-array is [Left = 1, Right = R1].
- Repeat the same process from step 2 for other values of Left and Right till Left < N.
Implementation:
C++
// C++ program Count total number of sub-arrays // having total distinct elements same as that // original array. #include<bits/stdc++.h> using namespace std; // Function to calculate distinct sub-array int countDistictSubarray( int arr[], int n) { // Count distinct elements in whole array unordered_map< int , int > vis; for ( int i = 0; i < n; ++i) vis[arr[i]] = 1; int k = vis.size(); // Reset the container by removing all elements vis.clear(); // Use sliding window concept to find // count of subarrays having k distinct // elements. int ans = 0, right = 0, window = 0; for ( int left = 0; left < n; ++left) { while (right < n && window < k) { ++vis[ arr[right] ]; if (vis[ arr[right] ] == 1) ++window; ++right; } // If window size equals to array distinct // element size, then update answer if (window == k) ans += (n - right + 1); // Decrease the frequency of previous element // for next sliding window --vis[ arr[left] ]; // If frequency is zero then decrease the // window size if (vis[ arr[left] ] == 0) --window; } return ans; } // Driver code int main() { int arr[] = {2, 1, 3, 2, 3}; int n = sizeof (arr) / sizeof (arr[0]); cout << countDistictSubarray(arr, n) << "n" ; return 0; } |
Java
// Java program Count total number of sub-arrays // having total distinct elements same as that // original array. import java.util.HashMap; class Test { // Method to calculate distinct sub-array static int countDistictSubarray( int arr[], int n) { // Count distinct elements in whole array HashMap<Integer, Integer> vis = new HashMap<Integer,Integer>(){ @Override public Integer get(Object key) { if (!containsKey(key)) return 0 ; return super .get(key); } }; for ( int i = 0 ; i < n; ++i) vis.put(arr[i], 1 ); int k = vis.size(); // Reset the container by removing all elements vis.clear(); // Use sliding window concept to find // count of subarrays having k distinct // elements. int ans = 0 , right = 0 , window = 0 ; for ( int left = 0 ; left < n; ++left) { while (right < n && window < k) { vis.put(arr[right], vis.get(arr[right]) + 1 ); if (vis.get(arr[right])== 1 ) ++window; ++right; } // If window size equals to array distinct // element size, then update answer if (window == k) ans += (n - right + 1 ); // Decrease the frequency of previous element // for next sliding window vis.put(arr[left], vis.get(arr[left]) - 1 ); // If frequency is zero then decrease the // window size if (vis.get(arr[left]) == 0 ) --window; } return ans; } // Driver method public static void main(String args[]) { int arr[] = { 2 , 1 , 3 , 2 , 3 }; System.out.println(countDistictSubarray(arr, arr.length)); } } |
Python3
# Python3 program Count total number of # sub-arrays having total distinct elements # same as that original array. # Function to calculate distinct sub-array def countDistictSubarray(arr, n): # Count distinct elements in whole array vis = dict () for i in range (n): vis[arr[i]] = 1 k = len (vis) # Reset the container by removing # all elements vid = dict () # Use sliding window concept to find # count of subarrays having k distinct # elements. ans = 0 right = 0 window = 0 for left in range (n): while (right < n and window < k): if arr[right] in vid.keys(): vid[ arr[right] ] + = 1 else : vid[ arr[right] ] = 1 if (vid[ arr[right] ] = = 1 ): window + = 1 right + = 1 # If window size equals to array distinct # element size, then update answer if (window = = k): ans + = (n - right + 1 ) # Decrease the frequency of previous # element for next sliding window vid[ arr[left] ] - = 1 # If frequency is zero then decrease # the window size if (vid[ arr[left] ] = = 0 ): window - = 1 return ans # Driver code arr = [ 2 , 1 , 3 , 2 , 3 ] n = len (arr) print (countDistictSubarray(arr, n)) # This code is contributed by # mohit kumar 29 |
C#
// C# program Count total number of sub-arrays // having total distinct elements same as that // original array. using System; using System.Collections.Generic; class Test { // Method to calculate distinct sub-array static int countDistictSubarray( int []arr, int n) { // Count distinct elements in whole array Dictionary< int , int > vis = new Dictionary< int , int >(); for ( int i = 0; i < n; ++i) if (!vis.ContainsKey(arr[i])) vis.Add(arr[i], 1); int k = vis.Count; // Reset the container by removing all elements vis.Clear(); // Use sliding window concept to find // count of subarrays having k distinct // elements. int ans = 0, right = 0, window = 0; for ( int left = 0; left < n; ++left) { while (right < n && window < k) { if (vis.ContainsKey(arr[right])) vis[arr[right]] = vis[arr[right]] + 1; else vis.Add(arr[right], 1); if (vis[arr[right]] == 1) ++window; ++right; } // If window size equals to array distinct // element size, then update answer if (window == k) ans += (n - right + 1); // Decrease the frequency of previous element // for next sliding window if (vis.ContainsKey(arr[left])) vis[arr[left]] = vis[arr[left]] - 1; // If frequency is zero then decrease the // window size if (vis[arr[left]] == 0) --window; } return ans; } // Driver method public static void Main(String []args) { int []arr = {2, 1, 3, 2, 3}; Console.WriteLine(countDistictSubarray(arr, arr.Length)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript program Count total number of sub-arrays // having total distinct elements same as that // original array. // Method to calculate distinct sub-array function countDistictSubarray(arr,n) { // Count distinct elements in whole array let vis = new Map(); for (let i = 0; i < n; ++i) vis.set(arr[i], 1); let k = vis.size; // Reset the container by removing all elements let vid= new Map(); // Use sliding window concept to find // count of subarrays having k distinct // elements. let ans = 0, right = 0, window = 0; for (let left = 0; left < n; left++) { while (right < n && window < k) { if (vid.has(arr[right])) vid.set(arr[right], vid.get(arr[right]) + 1); else vid.set(arr[right], 1); if (vid.get(arr[right])== 1) window++; right++; } // If window size equals to array distinct // element size, then update answer if (window == k) ans += (n - right + 1); // Decrease the frequency of previous element // for next sliding window if (vid.has(arr[left])) vid.set(arr[left], vid.get(arr[left])- 1); // If frequency is zero then decrease the // window size if (vid.get(arr[left]) == 0) --window; } return ans; } // Driver method let arr=[2, 1, 3, 2, 3]; document.write(countDistictSubarray(arr, arr.length)); // This code is contributed by patel2127 </script> |
Output
5n
Time complexity: O(n)
Auxiliary space: O(n)
Contact Us