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: nums = [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: nums = [1,2,2,3,1,4,2]
Output: 6
Explanation: 
The degree is 3 because the element 2 is repeated 3 times.
So [2,2,3,1,4,2] is the shortest subarray, therefore returning 6.

 

Constraints:

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

---

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

'''
1. 아이디어 :
    Counter를 이용해서 각 숫자의 빈도수를 구하고 가장 높은 빈도수를 가진 숫자들을 구한다.
2. 시간복잡도 :
    O(n)
3. 자료구조 :
    리스트, 해시맵
'''


class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        a=Counter(nums)
        print(a)
        cmax=0
        candid=[]
        for key,val in a.items():
            cmax=max(cmax,val)
        for key,val in a.items():
            if val==cmax:
                candid.append(key)

        cmin=float('inf')
        l=0
        r=0
        for j in candid:
            for i in range(len(nums)-1):
                if nums[i]==j:
                    l=i
                    break
            for i in range(len(nums)-1,-1,-1):
                if nums[i]==j:
                    r=i
                    break
            cmin=min(cmin,r-l+1)
        return cmin