Problem Description
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.
Key Insights
- The degree of the array is determined by the element that appears most frequently.
- To find the shortest subarray with the same degree, we need to track the first and last occurrences of each element.
- A hash table (dictionary) can be used to count frequencies and store indices efficiently.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Solution
To solve this problem, we can use a hash table to keep track of the frequency of each element, as well as the first and last indices of each element's occurrence. The degree of the array is the maximum frequency found in the hash table. Once we know the degree, we can iterate through the hash table to find the minimum length of subarrays that have the same degree by calculating the difference between the last and first indices of the elements that have the maximum frequency.