Only One For Loop Consice Java solution with O(n) Time O(n) Space (Beats Almost 100%)


  • 0
    A

    We can check the frequency of each value and get the result as we traversal the array nums

        public int findShortestSubArray(int[] nums) {
            Map<Integer, int[]> degrees = new HashMap<>();
            int res = 1, degree = 1;
            for (int i = 0; i < nums.length; i++) {
                int[] record = degrees.get(nums[i]);
                if (record == null) {
                    degrees.put(nums[i], new int[]{1, i, i});
                    continue;
                }
                record[0]++;
                record[2] = i;
    
                if (degree < record[0]) {
                    degree = record[0];
                    res = i - record[1] + 1;
                } else if (degree == record[0]) {
                    res = Math.min(res, i - record[1] + 1);
                }
            }
            return res;
        }
    
    

Log in to reply
 

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