Java O(n) Time O(n) Space


  • 9
    1. Get degree of array, frequency of all integers in array, and the indices of the first and last occurrence of each integer in the array
    2. Return the minimum occurrence range of each integer which appears degree number of times in the array,
    public int findShortestSubArray(int[] nums) {
        int degree = 0, n = nums.length, minSize = n;
        Map<Integer, Integer> map = new HashMap<>();
        Map<Integer, Integer[]> map2 = new HashMap<>();
        
        for (int i=0;i<n;i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            degree = Math.max(degree, map.get(nums[i]));
    
            if (map2.get(nums[i]) == null) map2.put(nums[i], new Integer[2]);
            Integer[] numRange = map2.get(nums[i]);
            if (numRange[0] == null) numRange[0] = i;
            numRange[1] = i;
        }
    
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() != degree) continue;
            Integer[] range = map2.get(entry.getKey());
            minSize = Math.min(minSize, range[1] - range[0] + 1);  
        }
        return minSize;
    }
    

  • 0

    @compton_scatter

    Using single HashMap O(n) Solution

        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;
    }
    

  • 1
    W

    I think you don't need to go over the map after going the entire array.
    You could be checking who is the smallest subarray in the first loop.

     public int findShortestSubArray(int[] nums) {
            Map<Integer, int[]> db = new Hashtable<>();
            int size = nums.length;
            int degree = 0;
            int smallestSubarray = 50001;
            for (int i = 0; i < size; i++) {
                int[] data;
                if (db.containsKey(nums[i])) {
                    data = db.get(nums[i]);
                } else {
                    data = new int[3];
                    data[1] = i;
                }
                data[2] = i;
                data[0] += 1;
    
                db.put(nums[i], data);
                if (data[0] > degree) {
                    degree = data[0];
                    smallestSubarray = data[2] - data[1] + 1;
                }else if (degree == data[0]) {
                    smallestSubarray = data[2] - data[1] + 1 < smallestSubarray ? data[2] - data[1] + 1 : smallestSubarray;
                }
            }
    
            return smallestSubarray;
        }
    

Log in to reply
 

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