Problem Description

You are given a non-empty array of non-negative integers called nums. The degree of an array is defined as the maximum frequency of any element in that array (i.e., how many times the most frequent element appears).

Your task is to find the shortest contiguous subarray that has the same degree as the entire array nums.

For example:

• If nums = [1, 2, 2, 3, 1], the degree is 2 (both 1 and 2 appear twice)
• The shortest subarray with degree 2 could be [2, 2] with length 2, or [1, 2, 2, 3, 1] with length 5
• The answer would be 2 since [2, 2] is shorter

The solution works by:

1. First calculating the degree of the entire array using Counter to count element frequencies
2. Tracking the first and last occurrence positions of each element using left and right dictionaries
3. For each element that appears with maximum frequency (degree), calculating the length of the subarray from its first to last occurrence
4. Returning the minimum length among all such subarrays

The key insight is that any subarray with the same degree as the original array must contain all occurrences of at least one element that appears with maximum frequency. Therefore, the shortest such subarray would span from the first to the last occurrence of one of these maximum-frequency elements.

Intuition

To understand this problem, let's think about what determines the degree of a subarray. The degree is the maximum frequency of any element, so if we want a subarray to have the same degree as the original array, it must contain at least one element that appears with that maximum frequency.

Here's the key observation: if an element appears k times in the original array (where k is the degree), then any subarray containing all k occurrences of this element will have degree at least k. Since we can't have a degree higher than the original array's degree, such a subarray will have exactly degree k.

This leads us to an important insight: the shortest subarray with the required degree must span from the first occurrence to the last occurrence of some element that has maximum frequency. Why? Because:

1. We need to include all occurrences of at least one maximum-frequency element to maintain the degree
2. Including anything before the first occurrence or after the last occurrence would only make the subarray longer without changing the degree
3. The optimal subarray is simply the tightest "window" that captures all occurrences of one such element

For example, if element x appears 5 times (which is the degree), and these occurrences are at positions [2, 4, 7, 9, 15], then the subarray from index 2 to 15 will have degree 5. We can't make it shorter because we'd lose some occurrences of x, reducing the degree.

Therefore, our strategy becomes: for each element that appears with maximum frequency, calculate the distance from its first to last occurrence, and take the minimum among all such distances. This gives us the shortest possible subarray with the same degree as the original array.

Solution Approach

The implementation uses a systematic approach with hash maps to efficiently track element positions and frequencies:

1. Count frequencies and find degree: We use Counter(nums) to create a frequency map of all elements. Then cnt.most_common()[0][1] gives us the degree - the highest frequency among all elements.

2. Track first and last positions: We create two dictionaries:

   • left: stores the first occurrence index of each element
   • right: stores the last occurrence index of each element

   We iterate through the array once with enumerate(nums):

   for i, v in enumerate(nums):
       if v not in left:
           left[v] = i  # Record first occurrence
       right[v] = i     # Always update last occurrence

3. Find minimum subarray length: We iterate through nums and for each element v:

   • Check if its frequency equals the degree: cnt[v] == degree
   • If yes, calculate the subarray length from first to last occurrence: right[v] - left[v] + 1
   • Keep track of the minimum length found

4. Return result: The variable ans maintains the minimum length throughout the process. We initialize it to inf (infinity) to ensure any valid subarray length will be smaller.

The time complexity is O(n) where n is the length of the array, as we make three passes through the array (counting, position tracking, and finding minimum). The space complexity is also O(n) for storing the frequency map and position dictionaries.

The elegance of this solution lies in recognizing that we only need to check subarrays defined by elements with maximum frequency, rather than checking all possible subarrays, which would be much less efficient.

Example Walkthrough

Let's walk through the solution with nums = [1, 2, 2, 3, 1, 4, 2].

Step 1: Count frequencies and find degree

• Count each element: {1: 2, 2: 3, 3: 1, 4: 1}
• The degree is 3 (element 2 appears 3 times, which is the maximum)

Step 2: Track first and last positions

• As we iterate through the array:
  • Index 0, value 1: left[1] = 0, right[1] = 0
  • Index 1, value 2: left[2] = 1, right[2] = 1
  • Index 2, value 2: left[2] stays 1, right[2] = 2
  • Index 3, value 3: left[3] = 3, right[3] = 3
  • Index 4, value 1: left[1] stays 0, right[1] = 4
  • Index 5, value 4: left[4] = 5, right[4] = 5
  • Index 6, value 2: left[2] stays 1, right[2] = 6

Final dictionaries:

• left = {1: 0, 2: 1, 3: 3, 4: 5}
• right = {1: 4, 2: 6, 3: 3, 4: 5}

Step 3: Find minimum subarray length

• Check each element:
  • Element 1: frequency = 2 ≠ degree (3), skip
  • Element 2: frequency = 3 = degree ✓
    • Subarray length = right[2] - left[2] + 1 = 6 - 1 + 1 = 6
    • This represents subarray [2, 2, 3, 1, 4, 2] from index 1 to 6
  • Element 3: frequency = 1 ≠ degree (3), skip
  • Element 4: frequency = 1 ≠ degree (3), skip

Step 4: Return result

• Only element 2 has the maximum frequency
• The minimum (and only) valid subarray length is 6
• The subarray [2, 2, 3, 1, 4, 2] contains all three occurrences of 2, maintaining degree 3

The answer is 6.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

• Creating the Counter object takes O(n) time where n is the length of the input array
• Finding the most common element using most_common()[0][1] takes O(n) time as it needs to iterate through all unique elements
• The first loop to build the left and right dictionaries iterates through all n elements once, taking O(n) time
• The second loop iterates through all n elements in nums, and for each element, it performs constant time operations (dictionary lookups and comparisons), resulting in O(n) time
• Overall time complexity: O(n) + O(n) + O(n) + O(n) = O(n)

Space Complexity: O(n)

• The Counter object cnt stores at most n key-value pairs in the worst case (when all elements are unique), requiring O(n) space
• The left dictionary stores at most n key-value pairs in the worst case, requiring O(n) space
• The right dictionary stores at most n key-value pairs in the worst case, requiring O(n) space
• Overall space complexity: O(n) + O(n) + O(n) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Duplicate Checking in the Final Loop

The current implementation iterates through the entire nums array in the final loop, potentially checking the same value multiple times. For example, if nums = [1,1,1,2,2,2], we check value 1 three times and value 2 three times, performing redundant calculations.

Solution: Instead of iterating through nums, iterate through unique values only:

# Instead of:
for value in nums:
    if frequency_map[value] == max_frequency:
        # ...

# Use:
for value in frequency_map:
    if frequency_map[value] == max_frequency:
        # ...

2. Handling Edge Cases with Single Element Arrays

While the problem states the array is non-empty, if the array has only one element like nums = [1], the code works but could be optimized with an early return.

Solution: Add an early check:

if len(nums) == 1:
    return 1

3. Multiple Elements with Same Maximum Frequency

A subtle pitfall is not recognizing that multiple different elements can have the same maximum frequency. The code handles this correctly, but developers might mistakenly optimize by breaking early after finding the first element with maximum frequency.

Incorrect optimization:

for value in frequency_map:
    if frequency_map[value] == max_frequency:
        return last_occurrence[value] - first_occurrence[value] + 1
        # Wrong! This returns the first found, not necessarily the shortest

Correct approach: Always check all elements with maximum frequency to find the minimum length.

4. Memory Optimization Opportunity

The code creates both first_occurrence and last_occurrence dictionaries separately, but they could be combined into a single dictionary storing tuples:

Optimized version:

positions = {}
for index, value in enumerate(nums):
    if value not in positions:
        positions[value] = [index, index]
    else:
        positions[value][1] = index

This reduces the number of dictionary lookups and slightly improves memory usage.