Count subarrays having total distinct elements same as original array

Last Updated : 09 Mar, 2023

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

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

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)

S

Shubham Bansal

Improve

Previous Article

Cuckoo Hashing - Worst case O(1) Lookup!

Maximum array from two given arrays keeping order same

Similar Reads

Count distinct sequences obtained by replacing all elements of subarrays having equal first and last elements with the first element any number of times

Given an array arr[] consisting of N integers, the task is to find the number of different sequences that can be formed after performing the below operation on the given array arr[] any number of times. Choose two indices i and j such that arr[i] is equal to arr[j] and update all the elements in the range [i, j] in the array to arr[i]. Examples: In

Construct original array starting with K from an array of XOR of all elements except elements at same index

Given an array A[] consisting of N integers and first element of the array B[] as K, the task is to construct the array B[] from A[] such that for any index i, A[i] is the Bitwise XOR of all the array elements of B[] except B[i]. Examples: Input: A[] = {13, 14, 10, 6}, K = 2Output: 2 1 5 9Explanation:For any index i, A[i] is the Bitwise XOR of all

Count subarrays having at least X distinct elements that occur exactly Y times

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:10Explanation:Subarrays with at least X distinct elements occurring exactly Y times are: {2, 1, 2, 5, 3, 1}

Count of subarrays having exactly K distinct elements

Given an array arr[] of size N and an integer K. The task is to find the count of subarrays such that each subarray has exactly K distinct elements. Examples: Input: arr[] = {2, 1, 2, 1, 6}, K = 2 Output: 7 {2, 1}, {1, 2}, {2, 1}, {1, 6}, {2, 1, 2}, {1, 2, 1} and {2, 1, 2, 1} are the only valid subarrays. Input: arr[] = {1, 2, 3, 4, 5}, K = 1 Outpu

Count subarrays having a single distinct element that can be obtained from a given array

Given an array arr[] of size N, the task is to count the number of subarrays consisting of a single distinct element that can be obtained from a given array. Examples: Input: N = 4, arr[] = { 2, 2, 2, 2 }Output: 7Explanation: All such subarrays {{2}, {2}, {2}, {2}, {2, 2}, {2, 2, 2}, {2, 2, 2, 2}}. Therefore, total count of such subarrays are 7. In

Count number of permutation of an Array having no SubArray of size two or more from original Array

Given an array of distinct integer A, the task is to count the number of possible permutations of the given array A[] such that the permutations do not contain any subarray of size 2 or more from the original array.Examples: Input: A = [ 1, 3, 9 ] Output: 3 All the permutation of [ 1, 3, 9 ] are : [ 1, 3, 9 ], [ 1, 9, 3 ], [ 3, 9, 1 ], [ 3, 1, 9 ],

Construct an Array having K Subarrays with all distinct elements

Given integers N and K, the task is to construct an array arr[] of size N using numbers in the range [1, N] such that it has K sub-arrays whose all the elements are distinct. Note: If there are multiple possible answers return any of them. Examples: Input: N = 5, K = 8Output: {1, 2, 3, 3, 3}Explanation: This array has the distinct sub-arrays as {1}

Count subarrays having each distinct element occurring at least twice

Given an array arr[] of size N, the task is to count the number of subarrays from the given array, such that each distinct element in these subarray occurs at least twice. Examples: Input: arr[] = {1, 1, 2, 2, 2}Output: 6Explanation: Subarrays having each element occurring at least twice are :{{1, 1}, {1, 1, 2, 2}, {1, 1, 2, 2, 2}, {2, 2}, {2, 2, 2

Maximum sum of subarrays having distinct elements of length K

Given an array, arr[] and a value k, represent the length of the subarray to be considered. Find the maximum sum that can be obtained from the subarray of length k such that each element of the subarray is unique. If there is no subarray that meets the required condition then return 0. Examples: Input: arr[] = {1, 5, 4, 2, 9, 9, 9}, k = 3Output: 15

Find total number of positions in all Subarrays such that position and value are same

Given an array A[] of size N, the task is to find the total number of positions in all the subarrays such that the value and position are the same. Examples: Input: A[] = {1, 2}Output: 3?Explanation: Following are the subarrays: In the subarray A[1, 1] = [1], elementat position 1 is 1.In the subarray A[1, 2] = [1, 2], for both the elements the cond

Article Tags :

Practice Tags :