Degree of an Array - Solution & Explanation
Problem Statement
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.lengthwill be between 1 and 50,000.nums[i]will be an integer between 0 and 49,999.
Approach Overview
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 1: Using HashMap to Track Frequencies and Positions
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.
This C solution uses arrays to mimic hashmaps due to the constraints. It keeps count of each element's frequency and notes their first and last occurrence. It calculates the degree, then finds the shortest subarray with that degree.
Complexity
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.
Approach 2: Two-Pass Array Traversal
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.
This C implementation involves keeping separate indices arrays for the first and last index occurrences of elements in a straightforward fashion. It performs a thorough scan and uses array indices to track positions.
Complexity
Time Complexity: O(n), needing two passes over n elements.
Space Complexity: O(n), primarily due to the need to store index locations.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Using HashMap to Track Frequencies and Positions | Time Complexity: O(n), where n is the number of elements in the array. |
| Two-Pass Array Traversal | Time Complexity: O(n), needing two passes over n elements. |
| Default Approach | — |
Detailed Complexity Analysis
| 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. |
Video Solution
LeetCode 697. Degree of an Array (Algorithm Explained) • Nick White • 24,446 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Degree of an Array easy or hard?
How to solve Degree of an Array in O(n)?
What is the best approach for Degree of an Array?
Is Degree of an Array asked at Google/Amazon/Meta?
What data structure is used in Degree of an Array?
What is the time complexity of Degree of an Array?
Degree of an Array Python or Java solution approach?
Ready to solve this problem?
Practice Degree of an Array with our built-in code editor and test cases.
Practice on FleetCode