697. Degree of an Array

Approach 1: Storing Count, Left and Right Index

For each unique number in the array we can keep track of the number of times it occurs along with its leftmost and rightmost index. If the maximum count occurs only once then we can return the difference between right most and left most index and if the max count occurs more than once we can return the minimum of the right most and left most index

def findShortestSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
di = {}
le = len(nums)
for i in range(le):
if nums[i] not in di:
di[nums[i]] = [1,i,i]
else:
di[nums[i]][2] = i
di[nums[i]][0] += 1
ma, ans = -1, float('inf')
for i in di:
if di[i][0] > ma:
ma = di[i][0]
ans = di[i][2] - di[i][1] + 1
elif di[i][0] == ma and ans > di[i][2] - di[i][1] + 1:
ma = di[i][0]
ans = di[i][2] - di[i][1] + 1
return ans

This solution passes all the test cases and runs pretty snappily coming in at a solid 93.3% percentile with a runtime of 80ms

Some minor improvements such as using defaultdict in the collections library to handle the insertion better. Another optimization would be to use comparison between tuples to find the max count and the min degree faster. Implementing all these results in the following solution

from collections import defaultdict
def findShortestSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
map = defaultdict(list)
for i in range(len(nums)):
map[nums[i]].append(i)
# print(list((-len(list), list[-1] - list[0] + 1) for list in map.values()))
return min((-len(list), list[-1] - list[0] + 1) for list in map.values())[1]

This solution comes in at 98% percentile with a runtime of 72ms, notice the smart use of the tuples generator to solve the problem efficiently