# 697. Degree of an Array
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
# Solution
Approach 1: just do it XD
# Code (Python)
Approach 1:
class Solution:
def findShortestSubArray(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
max_freq = 0
max_freq_nums = []
freqs = {}
for i, num in enumerate(nums):
if num not in freqs:
freqs[num] = [] # or just record (first_occurence_index, last_occurence_index, num_occurences)
freqs[num].append(i)
if len(freqs[num]) > max_freq:
max_freq = len(freqs[num])
max_freq_nums = [num]
elif len(freqs[num]) == max_freq:
max_freq_nums.append(num)
return min(freqs[num][-1] - freqs[num][0] + 1 for num in max_freq_nums)
# Code (C++)
Approach 1:
Approach 2: