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.

Difficulty: introductory

Starter code:

class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
     def findShortestSubArray(self, nums):
         
         diction = {}
         
         for i in nums:
             if i not in diction:
                 diction[i] = 1
             else:
                 diction[i] += 1
             
         degree = max(list(diction.values()))
         
         if degree == 1:
             return 1
         
         max_value = []
         
         for i in diction:
             if diction[i] == degree:
                 max_value.append(i)
         
         min_length = 10000000000
         
         for i in max_value:
             head = 0
             tail = 0
             for j in range(len(nums)):
                 if nums[j] == i:
                     head = j
                     break
             for j in range(len(nums)-1,-1,-1):
                 if nums[j] == i:
                     tail = j
                     break
             if min_length > tail - head + 1:
                 min_length = tail - head + 1
         
         return min_length

class Solution:
     def findShortestSubArray(self, nums):
         
         diction = {}
         
         for i in nums:
             if i not in diction:
                 diction[i] = 1
             else:
                 diction[i] += 1
             
         degree = max(list(diction.values()))
         
         if degree == 1:
             return 1
         
         max_value = []
         
         for i in diction:
             if diction[i] == degree:
                 max_value.append(i)
         
         min_length = 10000000000
         
         for i in max_value:
             head = 0
             tail = 0
             for j in range(len(nums)):
                 if nums[j] == i:
                     head = j
                     break
             for j in range(len(nums)-1,-1,-1):
                 if nums[j] == i:
                     tail = j
                     break
             if min_length > tail - head + 1:
                 min_length = tail - head + 1
         
         return min_length

class Solution:
     def findShortestSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         import collections
         c = collections.Counter(nums)
         degree = max(c[n] for n in c)
         if degree <=1:
             return degree
         res = {}
         for n in c:
             if c[n] == degree:
                 res[n] = [-1,-1]
         for i,n in enumerate(nums):
             if n in res:
                 if res[n][0] == -1 :
                     res[n][0] = i
                 else:
                     res[n][1] = i
         return min(res[i][1]-res[i][0] for i in res) + 1

class Solution:
     def findShortestSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         c = collections.Counter(nums)
         first, last = {}, {}
         for i, v in enumerate(nums):
             first.setdefault(v, i)
             last[v] = i
         degree = max(c.values())
         return min(last[v] - first[v] + 1 for v in c if c[v] == degree)

class Solution:
     def findShortestSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         left, right, count = {}, {}, {}
         for i, x in enumerate(nums):
             if x not in left: left[x] = i
             right[x] = i
             count[x] = count.get(x, 0) + 1
 
         ans = len(nums)
         degree = max(count.values())
         for x in count:
             if count[x] == degree:
                 ans = min(ans, right[x] - left[x] + 1)
 
         return ans

class Solution:
     def findShortestSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         left, right, count = {}, {}, {}
         for i, x in enumerate(nums):
             if x not in left: left[x] = i
             right[x] = i
             count[x] = count.get(x, 0) + 1
 
         ans = len(nums)
         degree = max(count.values())
         for x in count:
             if count[x] == degree:
                 ans = min(ans, right[x] - left[x] + 1)
 
         return ans

class Solution:
     def findShortestSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         cnt = {}
         se = {}
         cur_max_cnt = 0
         cur_span = float('inf')
         for idx, n in enumerate(nums):
             if not n in se:
                 se[n] = [idx, idx]
                 cnt[n] = 1
             else:
                 se[n][1] = idx
                 cnt[n] += 1
             x, y = se[n]
             if cnt[n] > cur_max_cnt or (cnt[n] == cur_max_cnt and y - x + 1 < cur_span):
                 cur_max_cnt = cnt[n]
                 cur_span = y - x + 1
         return cur_span

class Solution:
     def findShortestSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         d = {}
         for i in range(len(nums)):
             tmp = d.get(nums[i], [])
             tmp.append(i)
             d[nums[i]] = tmp
         low = []
         c = 0
         for k in d:
             tc = len(d.get(k))
             if tc > c:
                 c = tc
         for k in d:
             if len(d.get(k)) == c:
                 low.append(k)
 
         result = len(nums)
         for s in low:
             tmp = d.get(s)[-1] - d.get(s)[0] + 1 
             if tmp < result:
                 result = tmp
         return result

class Solution:
     def findShortestSubArray(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         r={}
         for i,j in enumerate(nums):
             if j not in r:
                 r[j]=1+100000*i
             else:
                 r[j]=r[j]%10000000000+1+10000000000*i
         tem=1
         dist=500000
         print(r)
         for i in list(r.values()):
             print(i)
             if i%100000==tem:
                 if tem==1:
                     dist=1
                 else:
                     dist_tem=i//10000000000-(i//100000)%100000+1
                     if dist_tem<dist:
                         dist=dist_tem
             elif i%100000>tem:
                 tem=i%100000
                 dist=i//10000000000-(i//100000)%100000+1
         return dist
             
                 
        #  x=[0 for i in range(50000)]
        #  for i in range(len(nums)):
        #      x[nums[i]]=x[nums[i]]+1
        #      if x[nums[i]]==1:
        #          x[nums[i]]=x[nums[i]]+100000*i
        #      else:
        #          x[nums[i]]=x[nums[i]]%10000000000+10000000000*i
        #  tem=1
        # # print(x)
        #  dist=50000
        #  for i in x:
        #     # print(i)
        #      if i>0:
        #          if i%100000==tem:
        #              tem=i%100000
        #              if tem==1:
        #                  dist=1
        #              else:
        #                  dist_tem=i//10000000000-(i//100000)%100000+1
        #                  if dist_tem<dist:
        #                      dist=dist_tem
        #          elif i%100000>tem:
        #              tem=i%100000
        #              dist=i//10000000000-(i//100000)%100000+1
        #         # print(dist)
        #  return dist