Count subarrays having total distinct elements same as original array

Given an array of n integers. Count total number of sub-array having total distinct elements same as that of total distinct elements of 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 it with total distinct elements of original array. This approach takes O(n²) time.

An efficient approach is to use 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 range [Left=0, Right] equal to k(or window size would not equal to k), let this right be R₁. Now since the sub-array [Left = 0, R₁] has k distinct elements, so all the sub-arrays starting at Left = 0 and ending after R₁ will also have k distinct elements. Thus add N-R₁+1 to the answer because [Left.. R₁], [Left.. R₁+1], [Left.. R₁+2] … [Left.. N-1] contains all the distinct numbers.
Now keeping R₁ 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 = R₁].
Repeat the same process from step 2 for other values of Left and Right till Left < N.

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 

Output:
5

Time complexity: O(n)
Auxiliary space: O(n)

Count subarrays having total distinct elements same as original array

C++

Java

Python3

tags:

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books