## Similar Problems

Similar Problems not available

# Degree Of An Array - Leetcode Solution

## Companies:

LeetCode: Degree Of An Array Leetcode Solution

Difficulty: Easy

Topics: hash-table array

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:

- Find the degree of the array, i.e., the maximum frequency of any one of its elements.
- Create a dictionary freq to store the frequency of each element of the array nums.
- Iterate through nums and update freq.
- Create a dictionary firstIdx to store the index of the first occurrence of each element of nums.
- Create a dictionary lastIdx to store the index of the last occurrence of each element of nums.
- Initialize minLength to be the length of nums.
- 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.
- 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.

## Degree Of An Array Solution Code

`1`