# 697. Degree of an Array

Easy

## Description

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Example 1:

Input: [1, 2, 2, 3, 1]

Output: 2

**Explanation: **

The input array has a degree of 2 because both elements 1 and 2 appear twice.

Of the subarrays that have the same degree:

[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]

The shortest length is 2. So return 2.

Example 2:

Input: [1,2,2,3,1,4,2]

Output: 6

Note:

• nums.length will be between 1 and 50,000.
• nums[i] will be an integer between 0 and 49,999.

## Solution

First get each number’s frequency in array nums. Next obtain the numbers with the maximum frequency. Then for each number with the maximum frequency, obtain the first occurrence minIndex and the last occurrence maxIndex of the number, and the subarray with this number has length maxIndex - minIndex + 1. Finally, return the minimum possible length among the subarrays of each number with maximum frequency.

Java

class Solution {
public int findShortestSubArray(int[] nums) {
Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();
int maxFrequency = 0;
for (int num : nums) {
int frequency = frequencyMap.getOrDefault(num, 0);
frequency++;
maxFrequency = Math.max(maxFrequency, frequency);
frequencyMap.put(num, frequency);
}
Set<Integer> maxFrequencySet = new HashSet<Integer>();
Set<Integer> keySet = frequencyMap.keySet();
for (int num : keySet) {
int frequency = frequencyMap.getOrDefault(num, 0);
if (frequency == maxFrequency)
}
Map<Integer, List<Integer>> numIndicesMap = new HashMap<Integer, List<Integer>>();
int length = nums.length;
for (int i = 0; i < length; i++) {
int num = nums[i];
if (maxFrequencySet.contains(num)) {
List<Integer> indices = numIndicesMap.getOrDefault(num, new ArrayList<Integer>());
numIndicesMap.put(num, indices);
}
}
int minLength = length;
for (int num : maxFrequencySet) {
List<Integer> indices = numIndicesMap.getOrDefault(num, new ArrayList<Integer>());
int size = indices.size();
if (size > 0) {
int minIndex = indices.get(0), maxIndex = indices.get(size - 1);
minLength = Math.min(minLength, maxIndex - minIndex + 1);
}
}
return minLength;
}
}