Q35 PepCoding | Count Of Subarrays With Equal Number Of 0s 1s And 2s
Fri Jan 27 2023 11:13:20 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
import java.util.*;
public class Main {
public static int solution(int[] arr) {
//make a hashmap<key,index> and traverse the array and keep adding key in the hashmap
//if the key repeats that means equal number of 0's,1's & 2's are present
//update frequency of the repeated key as we have to find the count of substrings
int ans = 0;
HashMap<String,Integer> map = new HashMap<>();
int count0 = 0 , count1 =0 , count2 =0 ;
map.put("0#0" ,1 );
for(int i =0 ;i < arr.length ; i++){
//update counts
if(arr[i] == 0) count0++;
else if(arr[i] == 1) count1++;
else count2++;
//find difference in counts
int diff1 = count1-count0;
int diff2 = count2-count1;
//generate key
String val = diff1 +"#"+diff2;
//if key is already present,this key will make subarrays with already present keys in the HM which is represented by frequency
if(map.containsKey(val)){
ans += map.get(val);
}
//add the subarrays in ans and update the frequency
map.put(val , map.getOrDefault(val,0)+1);
}
return ans;
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scn.nextInt();
}
System.out.println(solution(arr));
}
}
content_copyCOPY
https://www.pepcoding.com/resources/data-structures-and-algorithms-in-java-levelup/hashmap-and-heaps/count-of-subarrays-with-equal-number-of-0s-1s-and-2s-official/ojquestion
Comments