LeetCode Solutions Blog

Degree of an Array

Number: 697

Difficulty: Easy

Paid? No

Problem Description

Given a non-empty array of non-negative integers, the degree of the array is defined as the maximum frequency of any one of its elements. The task is to determine the length of the smallest contiguous subarray that has the same degree as the original array.

Key Insights

Use a hash table (dictionary) to track the first and last indices of each element.
Use another hash table (or combine with the first) to count the frequency of each element.
The degree of the array is the highest frequency found.
For every element that achieves the maximum frequency, calculate the length of the subarray (last index - first index + 1) and return the minimum of these lengths.

Space and Time Complexity

Time Complexity: O(n) because the array is traversed only once. Space Complexity: O(n) because hash tables are used to store indices and frequencies for each unique element.

Solution

The solution involves a single pass through the array to capture key details for each element. We record:

The first occurrence index for each element.
The last occurrence index for each element.
The frequency count for each element. After processing the array, we determine the overall degree by taking the maximum frequency. For all elements that have this frequency, we compute the length of the subarray spanning from their first to last occurrence. The smallest of these lengths is the required answer.

Code Solutions

# Python solution
def findShortestSubArray(nums):
    # Dictionaries to store the first and last indices and the frequency count of each element.
    first_occurrence = {}
    last_occurrence = {}
    count = {}

    # Loop through the array to record the details.
    for i, num in enumerate(nums):
        if num not in first_occurrence:
            first_occurrence[num] = i  # record the first occurrence index
        last_occurrence[num] = i         # update the last occurrence index
        count[num] = count.get(num, 0) + 1  # increment the frequency for the number

    # Determine the degree of the array (maximum frequency).
    degree = max(count.values())

    # Initialize the result with a high value.
    min_length = len(nums)

    # For each element, if its frequency matches the degree, check the subarray length.
    for num in count:
        if count[num] == degree:
            current_length = last_occurrence[num] - first_occurrence[num] + 1
            min_length = min(min_length, current_length)

    return min_length

# Example usage:
print(findShortestSubArray([1,2,2,3,1]))  # Output should be 2
print(findShortestSubArray([1,2,2,3,1,4,2]))  # Output should be 6