Degree Of An Array - Leetcode Solution

Problem Statement: 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. To find the smallest possible length of a contiguous subarray with the same degree, we need to find the subarray that contains both 1 and 2. For example, the subarray [2,2,3,1] has a degree of 2 and the length of this subarray is 4. Therefore, the answer is 2, because the subarray [2,2] has the same degree as the input array and is the smallest possible subarray with this property.

Example 2: Input: nums = [1,2,2,3,1,4,2] Output: 6

Approach:

1. Find the degree of the array, i.e., the maximum frequency of any one of its elements.
2. Create a dictionary freq to store the frequency of each element of the array nums.
3. Iterate through nums and update freq.
4. Create a dictionary firstIdx to store the index of the first occurrence of each element of nums.
5. Create a dictionary lastIdx to store the index of the last occurrence of each element of nums.
6. Initialize minLength to be the length of nums.
7. Iterate through freq, and for each element x and its frequency f: i) If f is less than the current degree, continue to the next element in freq. ii) If f is equal to the current degree, compute the length of the subarray that starts at the first occurrence of x and ends at the last occurrence of x. iii) If the length of this subarray is less than minLength, update minLength.
8. Return minLength.

Solution:

class Solution: def findShortestSubArray(self, nums: List[int]) -> int: freq = {} firstIdx = {} lastIdx = {} for i in range(len(nums)): x = nums[i] if x not in freq: freq[x] = 0 firstIdx[x] = i freq[x] += 1 lastIdx[x] = i degree = max(freq.values()) minLength = len(nums) for x in freq: if freq[x] < degree: continue else: length = lastIdx[x] - firstIdx[x] + 1 if length < minLength: minLength = length return minLength

Time Complexity: O(n), where n is the length of nums. Space Complexity: O(n), for the use of the dictionaries freq, firstIdx and lastIdx.

1