Watch 10 video solutions for Degree of an Array, a easy level problem involving Array, Hash Table. This walkthrough by Nick White has 24,228 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: You are given an integer array. The degree of the array is the maximum frequency of any element. The task is to find the length of the smallest contiguous subarray that has the same degree as the entire array.
Approach 1: Using HashMap to Track Frequencies and Positions (O(n) time, O(n) space)
The key observation: the degree depends on the element with the highest frequency, but the answer depends on the distance between that element's first and last occurrence. Traverse the array once and maintain three hash maps (or dictionaries): one for frequency, one for the first index where each number appears, and one for the last index. Each time you see a number, increment its count and update its last position. After traversal, compute the degree and evaluate the subarray length for elements that reach that degree using lastIndex - firstIndex + 1. Hash lookups make each update O(1), so the full pass is O(n). This approach is the most direct and works well whenever you need to track frequencies and positions in an hash table.
Approach 2: Two-Pass Array Traversal (O(n) time, O(n) space)
This version separates the frequency calculation from the subarray length calculation. In the first pass, iterate through the array and compute the frequency of each element using a hash map while tracking the overall degree. In the second pass, record the first occurrence of each number and update the minimum window length whenever that number reaches the array's degree. The logic focuses only on elements that match the degree, which simplifies reasoning during interviews. The time complexity remains O(n) because each element is processed a constant number of times, and the hash map stores up to n distinct values, resulting in O(n) space.
Recommended for interviews: The HashMap frequency and position tracking approach is what most interviewers expect. It demonstrates that you recognize the relationship between element frequency and the minimal window containing all occurrences. Starting with the idea of counting frequencies shows baseline understanding, but extending it to track first and last positions proves you can translate observations into an optimal O(n) solution using hash-based lookups.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap to Track Frequencies and Positions | O(n) | O(n) | General case. Best approach when you need both frequency and index range information. |
| Two-Pass Array Traversal | O(n) | O(n) | Useful when you prefer separating frequency calculation from window evaluation for clarity. |