Skip to content

697. Degree Of An Array

Array Hash Table

Problem - Degree Of An Array

Easy

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: nums = [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: nums = [1,2,2,3,1,4,2]
Output: 6
Explanation: 
The degree is 3 because the element 2 is repeated 3 times.
So [2,2,3,1,4,2] is the shortest subarray, therefore returning 6.

 

Constraints:

  • nums.length will be between 1 and 50,000.
  • nums[i] will be an integer between 0 and 49,999.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        count = Counter(nums)
        degree = count.most_common()[0][1]
        result = float('inf')
        print(degree)

        left, right = {}, {}
        for i, val in enumerate(nums):
            if val not in left:
                left[val] = i
            right[val] = i

        for val in nums:
            if count[val] == degree:
                tmp = right[val] - left[val] + 1
                if result > tmp:
                    result = tmp

        return result

Submission Stats:

  • Runtime: 23 ms (46.36%)
  • Memory: 19.7 MB (40.10%)