697. Degree of an Array

 一刷 07/2022

Version #1 3 HashMaps

Time O(N)

Space O(N)

Runtime: 26 ms, faster than 66.81% of Java online submissions for Degree of an Array.

Memory Usage: 54.6 MB, less than 38.79% of Java online submissions for Degree of an Array.

class Solution {

    public int findShortestSubArray(int[] nums) {

        // key-number, value-frequency

        Map<Integer, Integer> freq = new HashMap<>();

        // key-number, value-first,last index of this number

        Map<Integer, Integer> leftIndex = new HashMap<>();

        Map<Integer, Integer> rightIndex = new HashMap<>();

        int maxFreq = 0;

        for (int i = 0; i < nums.length; i++) {

            int currFreq = freq.getOrDefault(nums[i], 0) + 1;

            maxFreq = Math.max(maxFreq, currFreq);

            freq.put(nums[i], currFreq);

            if (!leftIndex.containsKey(nums[i])) {

                leftIndex.put(nums[i], i);

            }

            rightIndex.put(nums[i], i);

        }

        int len = nums.length;

        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {

            int num = entry.getKey();

            if (entry.getValue() == maxFreq) {

                len = Math.min(len, rightIndex.get(num) - leftIndex.get(num) + 1);

            }

        }

        return len;

    }

}