Q32 Contiguous Array - LeetCode
Thu Jan 26 2023 21:22:29 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://leetcode.com/problems/contiguous-array/
Comments