Given an Array consisting of N integers, Count the number of contiguous subarrays where each element in the subarray appears 2 or more times.
Examples :
Input : n = 3 arr = [0, 0, 0] Output : 3 [0],[0],[0] - 0 [0,0],[0,0] - 2 [0,0,0] - 1 Total = 2 + 1 = 3 Input : n = 5 arr = [1, 2, 1, 2, 3] Output : 1 [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
Naive Approach :
It is the simplest approach. You iterate through all the subarrays and find the frequency of each subarray. Then check if the subarray is valid or not and keep track of all the subarrays by using a variable count.
Below is the implementation of above approach :
/*package whatever //do not write package name here */ import java.io.*; import java.util.*; class CPP { public static int countSubarrays(int a[], int n) { 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)) count++; } } // Return the count of subarrays return count; } public static boolean valid(HashMap<Integer, Integer> map) { // 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) < 2) return false; } return true; } // Driver Code public static void main(String[] args) { int n = 5; int a[] = { 1, 2, 1, 2, 3 }; System.out.println(countSubarrays(a, n)); } }
Output :
1
Efficient Approach :
The idea is to count all the subarrays with at least one element with frequency exactly one in the subarray. Then that subarray is not included in the count of valid subarrays. You can calculate all the subarrays by using the formula n*(n+1)/2. Remove all subarrays which satisfy the above condition.
Below is the implementation of above approach ::
/*package whatever //do not write package name here */ import java.io.*; import java.util.*; class CPP { public static int countSubarrays(int a[], int n) { if (n == 0) return 0; int count = (n * (n + 1)) / 2; HashMap<Integer, ArrayList<Integer> > map = new HashMap<>(); // To store the indices of each element for (int i = 0; i < n; i++) { if (map.get(a[i]) == null) map.put(a[i], new ArrayList<>()); ArrayList<Integer> curr = map.get(a[i]); curr.add(i); map.put(a[i], curr); } // Iterate through all keys and find invalid // subarrays count for (int key : map.keySet()) { for (int i = 0; i < map.get(key).size(); i++) { // to count the previous occurrence and next // occurrence of current element int left = -1, right = n; if (i - 1 >= 0) left = map.get(key).get(i - 1); if (i + 1 < map.get(key).size()) right = map.get(key).get(i + 1); int lc = i - left - 1; int rc = right - i + 1; if (lc == 0) count -= rc; else if (rc == 0) count -= lc; else count -= (lc * rc); } } // Return the count of subarrays return count; } // Driver Code public static void main(String[] args) { int n = 5; int a[] = { 1, 2, 1, 2, 3 }; System.out.println(countSubarrays(a, n)); } }
Output :
2
Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.