100 % Java O(n) Solution using single HashMap


  • -1

    Here I took single HashMap where an element is stored as key and its occurrences are stored as values in ArrayList.

    First, we iterate through the entire array and put all elements and its occurrences in the map. (while this we also keep track of maximum frequency in max variable).

    After this, we iterate through HashMap and find the size of arraylist which is equal to Max. After getting list, we subtract last and first element of list to get minimum length of subarray

    For Example
    nums= {1,2,3,2,1,2,1}
    index= 0 1 2 3 4 5 6
    the degree of the entire array is 1 or 2 (both occurs 3 times)

    Our HashMap will look like this

    Key(Integer) --->Value( List<Integer>)

    2--> [1,3,5] ( // indexes for element 2)
    3--> [2] ( // indexes for element 3)
    1-->[0,4,6] ( // indexes for element 1)

    Now we have two Lists which have size equal to 2 (ie degree of subarray equal to 2)

    Since we need to find minimum length of subarray, we can get it by taking difference between first and last element

    Coming back to HashMap again
    key--> Value
    2--> [1,3,5]
    3--> [2]
    1-->[0,4,6]

    So for Key 2 we get value as 5 (5-1+1) (LastIndex-FirstIndex+1)
    for Key 1 we get value as (6-0+1)(LastIndex-FirstIndex+1)

    so minimum value if 5 we return 5 as answer

        public int findShortestSubArray(int[] nums) {
          HashMap <Integer, List<Integer>> map = new HashMap <Integer, List<Integer>>();
            int max=0;
            for(int i=0; i<nums.length; i++){
                if(!map.containsKey(nums[i]))
                    map.put(nums[i],new ArrayList<Integer>());
                map.get(nums[i]).add(i);
              max=Math.max(max,map.get(nums[i]).size());
            }
            int min=nums.length;
            for(Map.Entry <Integer, List<Integer>> map1:map.entrySet()){
                if(map1.getValue().size()==max){
                    min=Math.min(min,map1.getValue().get(map1.getValue().size()-1)-map1.getValue().get(0)+1);
                }
            }
            
            
            return min;
      }
    

Log in to reply
 

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