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
Last updated