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

  • 0
    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++){
                map.put(nums[index], new ArrayList<>());
        // 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.