One pass, One HashMap solution in Java O(N)


  • 0
    R
        public int findShortestSubArray(int[] nums) {
            if(nums==null)
                return 0;
            if(nums.length < 2)
                return nums.length;
            Map<Integer,int[]> hash=new HashMap<Integer,int[]>();
            int max_degree=0;
            int len=0;
            for(int i=0;i<nums.length;i++){
                // Value Format is start,end,degree
                int[] res=new int[]{i,i,1};
                if(hash.containsKey(nums[i])){
                    res=hash.get(nums[i]);
                    res[1]=i;
                    res[2]++;
                }
                if(res[2] > max_degree){
                    max_degree=res[2];
                    len=res[1]-res[0]+1;
                }
                else if(res[2]==max_degree && len > res[1]-res[0]+1){
                    len=res[1]-res[0]+1;
                }
                hash.put(nums[i],res);
            }
            return len;
        }
    

Log in to reply
 

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