Q41 Degree of an Array - LeetCode
Sat Jan 28 2023 08:24:44 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int findShortestSubArray(int[] arr) {
//make 2 hashmaps to store frequency and store first occurance
HashMap<Integer,Integer> fmap = new HashMap<>();
HashMap<Integer,Integer> occur = new HashMap<>();
//make variables
int hf = 0; //highest frequency
// int s = 0 ; starting index which we will get from map2
// int e =0 ; ending index which we will get from current position
int len = Integer.MAX_VALUE; //length of smallest subarray
//travese the array
for(int i =0 ;i < arr.length ;i++){
int val = arr[i];
fmap.put(val,fmap.getOrDefault(val,0)+1); //updating frequency
if(occur.containsKey(val)==false) //storing first occurance
occur.put(val,i);
//if a higher frequency character exists update length
if(fmap.get(val) > hf){
hf = fmap.get(val);
int new_length = i - occur.get(val) +1;
len = new_length;
}
//if same frequency character exists store smaller length
else if(fmap.get(val) == hf){
int new_length = i - occur.get(val) +1;
len = Math.min(new_length,len);
}
}
return len;
}
}
content_copyCOPY
https://leetcode.com/problems/degree-of-an-array/
Comments