Degree of an Array

Difficulty: Easy | Acceptance: 58.30% | Paid: No Topics: Array, Hash Table

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.

• Examples
• Constraints
• Hash Map with First and Last Index
• Single Pass Tracking

Examples

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 the subarray [2,2,3,1,4,2] starting from index 1 and ending at index 6 has the same degree as nums. The length of this subarray is 6.

Constraints

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

Hash Map with First and Last Index

Intuition Track the frequency, first occurrence, and last occurrence of each element using hash maps, then find the minimum length among elements with maximum frequency.

Steps

• Create three hash maps: count, firstIndex, and lastIndex
• Iterate through the array, updating count and recording first/last indices
• Find the maximum frequency (degree)
• For all elements with this frequency, calculate the span (lastIndex - firstIndex + 1)
• Return the minimum span

class Solution:
    def findShortestSubArray(self, nums):
        count = {}
        first = {}
        last = {}
        
        for i, num in enumerate(nums):
            if num not in first:
                first[num] = i
            last[num] = i
            count[num] = count.get(num, 0) + 1
        
        degree = max(count.values())
        min_length = float('inf')
        
        for num in count:
            if count[num] == degree:
                min_length = min(min_length, last[num] - first[num] + 1)
        
        return min_length

Complexity

• Time: O(n) where n is the length of the array
• Space: O(n) for the hash maps
• Notes: Clean and readable solution with three hash maps

Single Pass Tracking

Intuition Track count, first index, and last index in a single pass while maintaining the current degree and minimum length.

Steps

• Use a single hash map to store count, first index, and last index for each element
• During iteration, update all three values
• Keep track of the current degree and minimum length
• Return the minimum length found

class Solution:
    def findShortestSubArray(self, nums):
        info = {}
        degree = 0
        min_length = float('inf')
        
        for i, num in enumerate(nums):
            if num not in info:
                info[num] = [1, i, i]  # [count, first, last]
            else:
                info[num][0] += 1
                info[num][2] = i
            
            count, first, last = info[num]
            
            if count > degree:
                degree = count
                min_length = last - first + 1
            elif count == degree:
                min_length = min(min_length, last - first + 1)
        
        return min_length

Complexity

• Time: O(n) where n is the length of the array
• Space: O(n) for the hash map
• Notes: Single pass solution that updates the answer dynamically