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(N3)
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.
- Iterate while r is less than N and the size of the set is at most K:
- 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 twiceint 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 Codeint 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 approachimport 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 twicedef 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 Codeif __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 approachusing 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 twicefunction 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 Codelet 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:
7
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
