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.

Source: leetcode | Difficulty: EASY
Tags: Data structures

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):
		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):
		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):
		(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):
		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):
		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):
		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