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. 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 [2,2,3,1,4,2] is the shortest subarray, therefore returning 6.
Constraints:
nums.length will be between 1 and 50,000.nums[i] will be an integer between 0 and 49,999.The key idea in #697 Degree of an Array is understanding the concept of an array's degree, which is the maximum frequency of any element. The goal is to find the shortest contiguous subarray that has the same degree as the entire array.
A practical approach uses a hash table to track three things while iterating through the array: the frequency of each element, its first occurrence index, and optionally its last occurrence. As you process the array, maintain the current maximum frequency (the array's degree).
Once the degree is known, examine the elements that achieve this frequency and compute the subarray length using their recorded positions. The minimum of these lengths is the answer. This method works efficiently because each element is processed only once and all lookups are constant time using a hash map.
Time complexity is O(n) for a single pass through the array, while space complexity is O(n) for storing frequency and index information.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map with frequency and index tracking | O(n) | O(n) |
| Single pass with first occurrence tracking | O(n) | O(n) |
Nick White
Use these hints if you're stuck. Try solving on your own first.
Say 5 is the only element that occurs the most number of times - for example, nums = [1, 5, 2, 3, 5, 4, 5, 6]. What is the answer?
This approach involves creating a HashMap for tracking the frequency of each element, and two other HashMaps to keep track of the first and last indices of each element. The goal is to determine the degree of the array, then find the shortest subarray that has this same degree.
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(n), due to the usage of the arrays to track counts and positions.
1function findShortestSubarray(nums) {
2 let count = {}, first = {}, last = {};
3 let degree = 0, minLen =
In JavaScript, we use objects as hashmaps to record counts, first positions, and last positions. This provides an efficient method to determine the shortest subarray meeting the degree condition.
This approach first calculates the degree of the array in a single pass, then performs a second traversal to identify the smallest contiguous subarray with the same degree. The second traversal uses the frequency and position data collected during the first pass.
Time Complexity: O(n), needing two passes over n elements.
Space Complexity: O(n), primarily due to the need to store index locations.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is commonly used in coding interviews to test understanding of hash maps, frequency counting, and array traversal. It also evaluates the ability to track multiple pieces of information in a single pass.
The optimal approach uses a hash map to track the frequency and first occurrence of each element while traversing the array. After determining the array's degree, compute the smallest subarray length among elements that reach this maximum frequency.
A hash table (or hash map) is the most suitable data structure because it allows constant-time updates and lookups for element frequencies and indices. This makes it efficient to track the degree and compute candidate subarray lengths.
Tracking the first occurrence helps determine the length of the smallest subarray that contains all instances contributing to the degree. By comparing the current index with the first index, you can compute the subarray length efficiently.
A JavaScript execution leveraging simple plain objects for hash management, enabling efficient consecutive passes to validate the shortest subarrays given collection degree.