Given an array, arr[] consisting of N integers and integer K, the task is to count the number of contiguous subarrays where each element is in the subarray at least K times.
Examples:
Input: N = 3, arr[] = {0, 0, 0}, K = 2
Output: 3
Explanation: [0], [0], [0] – 0
[0, 0], [0, 0] – 2
[0, 0, 0] – 1
total = 2 + 1 = 3Input: N = 5, arr = [1, 2, 1, 2, 3], K = 2
Output: 1
Explanation: [1] [2] [1] [2] [3] – 0
[1, 2] [2, 1] [1, 2] [2, 3] – 0
[1, 2, 1] [2, 1, 2] [1, 2, 3] – 0
[1, 2, 1, 2] [2, 1, 2, 3] – 1
[1, 2, 1, 2, 3] – 0
total = 1
Approach: This can be solved by the following idea:
The simplest approach is to iterate through all the subarrays and find the frequency of each subarray and check if the subarray is valid or not and keep track of all the subarrays by using a variable count.
Steps involved in the implementation of code:
- Maintain a Map while iterating over the arrays.
- Check for each subarray whether the frequency of each element is less than k or not.
- If it is greater than k, increment the count.
Below is the implementation of the above approach:
C++
// C++ Implementation#include<bits/stdc++.h>using namespace std;// Function to check whether sub-array // is valid or notbool valid(unordered_map<int, int>& map, int k){ // Iterate through all the keys in // the map check if the frequency // more than k or not for (auto key : map) { // Iterate through all the keys in // the map check if the frequency // more than 2 or not if (key.second < k) return false; } return true;}// Function to count sub-arraysint countSubarrays(int a[], int n, int k){ if (n == 0) return 0; int count = 0; // Iterate through all subarrays for (int i = 0; i < n; i++) { unordered_map<int, int> map; for (int j = i; j < n; j++) { // Check if given subarray // from i to j is valid map[a[j]]++; if (valid(map, k)) count++; } } // Return the count of subarrays return count;}// Driver Codeint main(){ int N = 5; int a[] = { 1, 2, 1, 2, 3 }; int K = 2; // Function call cout << countSubarrays(a, N, K) << endl; return 0;}// This code is contributed by Prasad Kandekar(prasad264) |
Java
// Java Implementationimport java.io.*;import java.util.*;class GFG { // Function to count sub-arrays public static int countSubarrays(int a[], int n, int k) { if (n == 0) return 0; int count = 0; // Iterate through all subarrays for (int i = 0; i < n; i++) { HashMap<Integer, Integer> map = new HashMap<>(); for (int j = i; j < n; j++) { // Check if given subarray // from i tp j is valid map.put(a[j], map.getOrDefault(a[j], 0) + 1); if (valid(map, k)) count++; } } // Return the count of subarrays return count; } // Function to check whether sub-array // is valid or not public static boolean valid(HashMap<Integer, Integer> map, int k) { // Iterate through all the keys in // the map check if the frequency // more than 2 or not for (int key : map.keySet()) { if (map.get(key) < k) return false; } return true; } // Driver Code public static void main(String[] args) { int N = 5; int a[] = { 1, 2, 1, 2, 3 }; int K = 2; // Function call System.out.println(countSubarrays(a, N, K)); }} |
Python3
# Python3 implementationdef valid(map, k): # Iterate through all the keys in # the map check if the frequency # more than k or not for key in map: # Iterate through all the keys in # the map check if the frequency # more than k or not if map[key] < k: return False return True# Function to count sub-arraysdef countSubarrays(a, n, k): if n == 0: return 0 count = 0 # Iterate through all subarrays for i in range(n): map = {} for j in range(i, n): # Check if given subarray # from i to j is valid if a[j] in map: map[a[j]] += 1 else: map[a[j]] = 1 if valid(map, k): count += 1 # Return the count of subarrays return count# Driver CodeN = 5a = [1, 2, 1, 2, 3]K = 2# Function callprint(countSubarrays(a, N, K)) |
C#
// C# Implementationusing System;using System.Collections.Generic;public class GFG { // Function to count sub-arrays public static int countSubarrays(int[] a, int n, int k) { if (n == 0) return 0; int count = 0; // Iterate through all subarrays for (int i = 0; i < n; i++) { Dictionary<int, int> map = new Dictionary<int, int>(); ; for (int j = i; j < n; j++) { // Check if given subarray // from i tp j is valid if (map.ContainsKey(a[j]) == false) map.Add(a[j], 1); else map[a[j]] += 1; if (valid(map, k)) count++; } } // Return the count of subarrays return count; } // Function to check whether sub-array // is valid or not public static bool valid(Dictionary<int, int> map, int k) { // Iterate through all the keys in // the map check if the frequency // more than 2 or not foreach(KeyValuePair<int, int> ele in map) { if (ele.Value < k) return false; } return true; } // Driver Code static public void Main() { int N = 5; int[] a = { 1, 2, 1, 2, 3 }; int K = 2; // Function call Console.WriteLine(countSubarrays(a, N, K)); }}// This code is contributed by Rohit Pradhan |
Javascript
// JavaScript Implementation// Function to check whether sub-array// is valid or notfunction valid(map, k) { // Iterate through all the keys in // the map check if the frequency // more than k or not for (let key of map.keys()) { // Iterate through all the keys in // the map check if the frequency // more than 2 or not if (map.get(key) < k) { return false; } } return true;}// Function to count sub-arraysfunction countSubarrays(a, n, k) { if (n == 0) { return 0; } let count = 0; // Iterate through all subarrays for (let i = 0; i < n; i++) { let map = new Map(); for (let j = i; j < n; j++) { // Check if given subarray // from i to j is valid map.set(a[j], (map.get(a[j]) || 0) + 1); if (valid(map, k)) { count++; } } } // Return the count of subarrays return count;}// Driver Codelet N = 5;let a = [1, 2, 1, 2, 3];let K = 2;// Function callconsole.log(countSubarrays(a, N, K));// This code is contributed by prasad264 |
Output
1
Time Complexity: O(N3)
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!