Very simple Java solution with O(n) time and O(n) space using HashMap


  • 0
    E
    public int findShortestSubArray(int[] nums) {
    
        Map<Integer, List<Integer>> map = new HashMap<>();
        // storing the index of each elements
        for(int index=0; index<nums.length; index++){
            if(!map.containsKey(nums[index]))
                map.put(nums[index], new ArrayList<>());
            map.get(nums[index]).add(index);
        }
        // see which element has the highest count
        int maxCount=0;
        for(Integer e:map.keySet())
            maxCount = Math.max(maxCount, map.get(e).size());
    
        int minLength = nums.length;
        // get these elements and compare to see which one has the shortest length if a sub array is to include them all
        for(Integer e:nums)
            if(map.get(e).size() == maxCount){
                int currLen = map.get(e).get(maxCount-1) - map.get(e).get(0)+1;
                minLength = Math.min(currLen, minLength);
            }
        return  minLength;
    }

Log in to reply
 

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