Q33 PepCoding | Count Of Subarrays With Equal Number Of Zeroes And Ones
Thu Jan 26 2023 21:24:18 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int findMaxLength(int[] nums) {
//treat 0's as -1 and 1 as 1 and keep finding PSA if PSA repeats anywhere then subarray between them will also be 0 compare that length and update answers
//use HM<Psa,Index> to store psa and their index
int psa=0 , max = 0 ; //psa = prefix sum array
HashMap<Integer,Integer> map = new HashMap<>();
map.put(0,-1);
for(int i = 0 ;i < nums.length ; i++){
int val = nums[i] == 0 ?-1 : 1 ;
psa += val;
if(map.containsKey(psa)){
int len = i - map.get(psa);
max = Math.max(max , len);
}
else
map.put(psa,i);
}
return max;
}
}
content_copyCOPY
https://www.pepcoding.com/resources/data-structures-and-algorithms-in-java-levelup/hashmap-and-heaps/count-of-subarrays-with-equal-number-of-zeroes-and-ones-official/ojquestion
Comments