Count subarrays having exactly K elements occurring at least twice

0 0 8 minutes read

Given an array arr[] consisting of N integers and a positive integer K, the task is to count the number of subarrays having exactly K elements occurring at least twice.

Examples:

Input: arr[] = {1, 1, 1, 2, 2}, K = 1
Output: 7
Explanation: The subarrays having exactly 1 element occurring at least twice are:

{1, 1}. Frequency of 1 is 2.

{1, 1, 1}. Frequency of 1 is 3.

{1, 1, 1, 2}. Frequency of 1 is 3.

{1, 1}. Frequency of 1 is 2.

{1, 1, 2}. Frequency of 1 is 2.

{1, 2, 2}. Frequency of 2 is 2.

{2, 2}. Frequency of 2 is 2.

Therefore, the required output is 7.

Input: arr[] = {1, 2, 1, 2, 3}, K = 3

Output: 0

Naive Approach: The simplest approach to solve this problem is to generate all possible subarrays from the given array and count those subarrays having exactly K elements occurring at least twice. After having checked for all the subarrays, print the total number of subarrays obtained.

Time Complexity: O(N³)
Auxiliary Space: O(N)

Efficient Approach: The above approach can be optimized by using Hashing and Two pointers technique. Follow the steps below to solve the problem:

Initialize a variable, say cntSub as 0, to store the count of all possible subarrays having exactly K elements occurring at least twice.
Initialize two variables, say l as 0, and r as 0, to store the indices of the left and the right boundaries of each subarray respectively.
Initialize a Map, say mp, and a Set, say S to store the count of elements in the subarrays and store the elements whose frequency in the subarray is at least 2 respectively.
Iterate until r is less than N and perform the following operations:
- Iterate while r is less than N and the size of the set is at most K:
  - Increment the count of arr[r] in mp and then push the element into set S if mp[arr[r]] is equal to 2.
  - Increment r by 1.
  - If the size of the set S is K then, increment the cntSub by 1.
- Iterate while l < r and the size of the set is greater than K:
  - Decrement the count of arr[l] in mp and then erase the element from set S if mp[arr[r]] is equal to 1.
  - Increment the cntSub and l by 1.
Now iterate while l < N and the size of the set is K and decrement the count of arr[l] by 1 and if the frequency of arr[l] is 1, then erase the arr[l] from the set.
After completing the above steps, print the value of cntSub as the resultant count of subarrays.

Below is the implementation of the above approach:

C++14

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the subarrays with
// exactly K elements occurring twice
int cntSubarrays(int A[], int K, int n)
{
    // Stores the count of subarrays
    // having exactly K elements
    // occurring at least twice
    int cntSub = 0;
 
    // Stores the count of
    // integers in the subarray
    map<int, int> mp;
 
    // Stores the indices of left
    // boundary and right boundary
    int l = 0, r = 0;
 
    // Store the elements which occurs
    // atleast twice between [l, r]
    set<int> st;
 
    // Iterate while r < n
    while (r < n) {
 
        // Iterate while r < n
        // and size of st <= K
        while (r < n && st.size() <= K) {
 
            // If mp[A[r]] >= 1
            if (mp[A[r]]) {
                st.insert(A[r]);
            }
 
            // Increment count of A[r]
            mp[A[r]]++;
 
            // Increment r by 1
            r++;
 
            // If st.size() is K
            if (st.size() == K)
                cntSub++;
        }
 
        // Iterate while l < r
        // and st.size() > K
        while (l < r && st.size() > K) {
 
            // Increment cntSub by 1
            cntSub++;
 
            // Decrement cntSub by 1
            mp[A[l]]--;
 
            // If mp[A[l]] = 1
            if (mp[A[l]] == 1) {
                st.erase(st.find(A[l]));
            }
 
            // Increment l by 1
            l++;
        }
    }
 
    // Iterate while l < n  and
    // st.size() == K
    while (l < n && st.size() == K) {
 
        // Increment cntSub by 1
        cntSub++;
 
        mp[A[l]]--;
 
        // If Mp[A[l]] is equal to 1
        if (mp[A[l]] == 1) {
            st.erase(st.find(A[l]));
        }
 
        // Increment l by 1
        l++;
    }
 
    // Return cntSub
    return cntSub;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 1, 1, 2, 2 };
    int K = 1;
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << cntSubarrays(arr, K, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
class GFG {
 
  // Function to count the subarrays with
  // exactly K elements occurring twice
  static int cntSubarrays(int[] A, int K, int n)
  {
 
    // Stores the count of subarrays
    // having exactly K elements
    // occurring at least twice
    int cntSub = 0;
 
    // Stores the count of
    // integers in the subarray
    HashMap<Integer, Integer> mp
      = new HashMap<Integer, Integer>();
 
    // Stores the indices of left
    // boundary and right boundary
    int l = 0, r = 0;
 
    // Store the elements which occurs
    // atleast twice between [l, r]
    HashSet<Integer> st = new HashSet<Integer>();
 
    // Iterate while r < n
    while (r < n) {
 
      // Iterate while r < n
      // and size of st <= K
      while (r < n && st.size() <= K) {
 
        // If mp[A[r]] >= 1
        if (mp.containsKey(A[r])) {
          st.add(A[r]);
        }
 
        // Increment count of A[r]
        if (mp.containsKey(A[r]))
          mp.put(A[r], mp.get(A[r]) + 1);
        else
          mp.put(A[r], 1);
 
        // Increment r by 1
        r++;
 
        // If st.size() is K
        if (st.size() == K)
          cntSub++;
      }
 
      // Iterate while l < r
      // and st.size() > K
      while (l < r && st.size() > K) {
 
        // Increment cntSub by 1
        cntSub++;
 
        // Decrement cntSub by 1
        if (mp.containsKey(A[l]))
          mp.put(A[l], mp.get(A[l]) - 1);
 
        // If mp[A[l]] = 1
        if (mp.get(A[l]) == 1) {
          st.remove(A[l]);
        }
 
        // Increment l by 1
        l++;
      }
    }
 
    // Iterate while l < n  and
    // st.size() == K
    while (l < n && st.size() == K) {
 
      // Increment cntSub by 1
      cntSub++;
      if (mp.containsKey(A[l]))
        mp.put(A[l], mp.get(A[l]) - 1);
 
      // If Mp[A[l]] is equal to 1
      if (mp.get(A[l]) == 1) {
        st.remove(A[l]);
      }
 
      // Increment l by 1
      l++;
    }
 
    // Return cntSub
    return cntSub;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int[] arr = { 1, 1, 1, 2, 2 };
    int K = 1;
    int N = arr.length;
 
    System.out.println(cntSubarrays(arr, K, N));
  }
}
 
// This code is contributed by ukasp.

Python3

# Python3 program for the above approach
 
# Function to count the subarrays with
# exactly K elements occurring twice
def cntSubarrays(A, K, n):
     
    # Stores the count of subarrays
    # having exactly K elements
    # occurring at least twice
    cntSub = 0
 
    # Stores the count of
    # integers in the subarray
    mp = {}
 
    # Stores the indices of left
    # boundary and right boundary
    l = 0
    r = 0
 
    # Store the elements which occurs
    # atleast twice between [l, r]
    st = set()
 
    # Iterate while r < n
    while (r < n):
         
        # Iterate while r < n
        # and size of st <= K
        while (r < n and len(st) <= K):
             
            # If mp[A[r]] >= 1
            if (A[r] in mp):
                st.add(A[r])
 
            # Increment count of A[r]
            if (A[r] in mp):
                mp[A[r]] += 1
            else:
                mp[A[r]] = 1
 
            # Increment r by 1
            r += 1
 
            # If st.size() is K
            if (len(st) == K):
                cntSub += 1
 
        # Iterate while l < r
        # and st.size() > K
        while (l < r and len(st) > K):
             
            # Increment cntSub by 1
            cntSub += 1
 
            # Decrement cntSub by 1
            if (A[l] in mp):
                mp[A[l]] -= 1
            else:
                mp[A[l]] = 1
  
            # If mp[A[l]] = 1
            if (mp[A[l]] == 1):
                st.remove(A[l])
 
            # Increment l by 1
            l += 1
 
    # Iterate while l < n  and
    # st.size() == K
    while (l < n and len(st) == K):
         
        # Increment cntSub by 1
        cntSub += 1
 
        mp[A[l]] -= 1
 
        # If Mp[A[l]] is equal to 1
        if (mp[A[l]] == 1):
            st.remove(A[l])
 
        # Increment l by 1
        l += 1
 
    # Return cntSub
    return cntSub
 
# Driver Code
if __name__ == '__main__':
     
    arr =  [1, 1, 1, 2, 2]
    K = 1
    N = len(arr)
     
    print(cntSubarrays(arr, K, N))
 
# This code is contributed by ipg2016107

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
  // Function to count the subarrays with
  // exactly K elements occurring twice
  static int cntSubarrays(int []A, int K, int n)
  {
     
    // Stores the count of subarrays
    // having exactly K elements
    // occurring at least twice
    int cntSub = 0;
 
    // Stores the count of
    // integers in the subarray
    Dictionary<int,int> mp = new Dictionary<int,int>();
 
    // Stores the indices of left
    // boundary and right boundary
    int l = 0, r = 0;
 
    // Store the elements which occurs
    // atleast twice between [l, r]
    HashSet<int> st = new HashSet<int>(); 
 
    // Iterate while r < n
    while (r < n) {
 
      // Iterate while r < n
      // and size of st <= K
      while (r < n && st.Count <= K) {
 
        // If mp[A[r]] >= 1
        if (mp.ContainsKey(A[r])) {
          st.Add(A[r]);
        }
 
        // Increment count of A[r]
        if (mp.ContainsKey(A[r]))
          mp[A[r]]++;
        else
          mp[A[r]] = 1;
 
        // Increment r by 1
        r++;
 
        // If st.size() is K
        if (st.Count == K)
          cntSub++;
      }
 
      // Iterate while l < r
      // and st.size() > K
      while (l < r && st.Count > K) {
 
        // Increment cntSub by 1
        cntSub++;
 
        // Decrement cntSub by 1
        if (mp.ContainsKey(A[l]))
          mp[A[l]]--;
 
        // If mp[A[l]] = 1
        if (mp[A[l]] == 1) {
          st.Remove(A[l]);
        }
 
        // Increment l by 1
        l++;
      }
    }
 
    // Iterate while l < n  and
    // st.size() == K
    while (l < n && st.Count == K) {
 
      // Increment cntSub by 1
      cntSub++;
      if (mp.ContainsKey(A[l]))
        mp[A[l]]--;
 
      // If Mp[A[l]] is equal to 1
      if (mp[A[l]] == 1) {
        st.Remove(A[l]);
      }
 
      // Increment l by 1
      l++;
    }
 
    // Return cntSub
    return cntSub;
  }
 
  // Driver Code
  public static void Main()
  {
    int []arr = { 1, 1, 1, 2, 2 };
    int K = 1;
    int N = arr.Length;
 
    Console.WriteLine(cntSubarrays(arr, K, N));
  }
}
 
// This code is contributed by ipg2016107.

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to count the subarrays with
// exactly K elements occurring twice
function cntSubarrays(A,K,n)
{
    // Stores the count of subarrays
    // having exactly K elements
    // occurring at least twice
    let cntSub = 0;
  
    // Stores the count of
    // integers in the subarray
    let mp = new Map();
  
    // Stores the indices of left
    // boundary and right boundary
    let l = 0, r = 0;
  
    // Store the elements which occurs
    // atleast twice between [l, r]
    let st = new Set();
  
    // Iterate while r < n
    while (r < n) {
  
      // Iterate while r < n
      // and size of st <= K
      while (r < n && st.size <= K) {
  
        // If mp[A[r]] >= 1
        if (mp.has(A[r])) {
          st.add(A[r]);
        }
  
        // Increment count of A[r]
        if (mp.has(A[r]))
          mp.set(A[r], mp.get(A[r]) + 1);
        else
          mp.set(A[r], 1);
  
        // Increment r by 1
        r++;
  
        // If st.size() is K
        if (st.size == K)
          cntSub++;
      }
  
      // Iterate while l < r
      // and st.size() > K
      while (l < r && st.size > K) {
  
        // Increment cntSub by 1
        cntSub++;
  
        // Decrement cntSub by 1
        if (mp.has(A[l]))
          mp.set(A[l], mp.get(A[l]) - 1);
  
        // If mp[A[l]] = 1
        if (mp.get(A[l]) == 1) {
          st.delete(A[l]);
        }
  
        // Increment l by 1
        l++;
      }
    }
  
    // Iterate while l < n  and
    // st.size() == K
    while (l < n && st.size == K) {
  
      // Increment cntSub by 1
      cntSub++;
      if (mp.has(A[l]))
        mp.set(A[l], mp.get(A[l]) - 1);
  
      // If Mp[A[l]] is equal to 1
      if (mp.get(A[l]) == 1) {
        st.delete(A[l]);
      }
  
      // Increment l by 1
      l++;
    }
  
    // Return cntSub
    return cntSub;
}
 
 // Driver Code
let arr=[1, 1, 1, 2, 2 ];
let K = 1;
let N = arr.length;
document.write(cntSubarrays(arr, K, N));
 
 
// This code is contributed by avanitrachhadiya2155
 
</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!