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.