Java Simple O(n) Solution with O(n) space.


  • 0
    S
    class Solution {
        public int findShortestSubArray(int[] nums) {
            HashMap<Integer, int[]> map = new HashMap<Integer, int[]>();
            int len = 0;
            /*In integer array first value is number of occurences, second is first occurence and third is last occurence*/
            int degree = 0;
            for(int i=0;i<nums.length;i++){
                if(!map.containsKey(nums[i]))
                    map.put(nums[i],new int[]{1,i,i});
                else{
                    int[] val = map.get(nums[i]);
                    map.put(nums[i], new int[]{val[0]+1, val[1], i});
                }
                int[] val = map.get(nums[i]);
                if(val[0]>degree)
                    len = val[2] - val[1] + 1;
                else{
                    if(val[0]==degree)
                        len = Math.min(val[2] - val[1] + 1, len);
                }
                degree = Math.max(val[0],degree);
            }
            
            return len;
            
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.