[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