LeetCode : 697. Degree of an Array

[congr]

https://leetcode.com/problems/degree-of-an-array/

[congr]

class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, List<Integer>> map = new HashMap();
        for (int i = 0; i < nums.length; i++) 
            map.computeIfAbsent(nums[i], k -> new ArrayList()).add(i);

        PriorityQueue<Integer> pq = 
            new PriorityQueue<>((a,b) -> map.get(b).size() - map.get(a).size());
        for (Integer key : map.keySet()) pq.add(key);

        int minRange = nums.length;
        int maxFreq = map.get(pq.peek()).size(); // degree
        while (!pq.isEmpty()) { // shortest range from same frequent values
            if (map.get(pq.peek()).size() < maxFreq) return minRange;

            List<Integer> list = map.get(pq.remove());
            minRange = Math.min(minRange, list.get(list.size()-1) - list.get(0) + 1);
        }

        return minRange;
    }
}

[congr]

Shorter

class Solution {
    public int findShortestSubArray(int[] nums) {
        int degree = 0;
        Map<Integer, List<Integer>> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            map.computeIfAbsent(nums[i], k -> new ArrayList()).add(i);
            degree = Math.max(degree, map.get(nums[i]).size()); // !!! size()
        }

        int minRange = nums.length;
        for (List<Integer> list : map.values()) {
            if (degree > list.size()) continue;

            minRange = Math.min(minRange, list.get(list.size()-1) - list.get(0) + 1);
        }

        return minRange;
    }
}