O(n) Java straight forward


  • 0
    J
    class Solution {
        public int findShortestSubArray(int[] nums) {
            Map<Integer, int[]> locMap = new HashMap<>();
            Map<Integer, Integer> freqMap = new HashMap<>();
            int maxFreq = 0;
            
            // Build maps
            for (int i = 0; i < nums.length; i++) {
                freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);
                maxFreq = Math.max(maxFreq, freqMap.get(nums[i]));
                
                if (!locMap.containsKey(nums[i])) {
                    locMap.put(nums[i], new int[2]);
                    int[] temp = locMap.get(nums[i]);
                    temp[0] = i;
                    temp[1] = i;
                    locMap.put(nums[i], temp);
                } else {
                    int[] temp = locMap.get(nums[i]);
                    temp[1] = i;
                    locMap.put(nums[i], temp);
                }
            }
            
            Set<Integer> maxSet = new HashSet<>();
            int minLen = nums.length;
            
            // Find all possible max freq values
            for (int i : freqMap.keySet()) {
                if (freqMap.get(i) == maxFreq) {
                    maxSet.add(i);
                }
            }
            
            // Result will be whichever number that has the highest frequency with the least distance between its first and last occurrence
            for (Map.Entry<Integer, int[]> e : locMap.entrySet()) {
                if (maxSet.contains(e.getKey())) {
                    minLen = Math.min(minLen, e.getValue()[1] - e.getValue()[0] + 1);
                }
            }
            
            return minLen;
        }
    }
    

Log in to reply
 

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