[LeetCode]#697. Degree of an Array

Environment: Python 3.7

Key technique: collections, Counter, enumerate, Dictionary

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

Analysis:

Use Collections module Counter to calculate frequency of number in Input and use Dictionary to record number start and end location.

Solution:

from collections import Counter
class Solution:
def findShortestSubArray(self, nums) -> int:
num_dict = Counter( nums )
max_num = max( list( num_dict.values() ) )
start_end = dict()
for index, x in enumerate(nums):
if x not in start_end:
start_end[x] = [index, index]
else:
start_index = start_end[x][0]
start_end[x] = [ start_index, index]

degree = len( nums )


for num, occ in num_dict.items():
if occ == max_num:

end_index = start_end[num][1]
start_index = start_end[num][0]
degree = min( degree, end_index - start_index + 1)

return degree

Submitted result:

Lesson learn:

It is difficult to record start and end location, so I refer code in leetcode website. enumerate and dictionary is good function to this problem.

Reference:

https://leetcode.com/problems/degree-of-an-array/discuss/476064/Python-O(-n-)-sol.-based-on-dictionary.-80%2B-With-explanation