Degree of an Array
Problem
Given a non-empty array of non-negative integers nums, return the length of the shortest contiguous subarray of nums that has the same degree as nums.
- 1 ≤ nums.length ≤ 5 * 10⁴
- 0 ≤ nums[i] ≤ 10⁵
Example
nums = [1, 2, 2, 3, 1]2The degree of the array is 2 because both elements 1 and 2 appear twice. The shortest subarray with degree 2 for element 1 is [1, 2, 2, 3, 1] (length 5), but for element 2 it is [2, 2] (length 2). The algorithm tracks the first and last occurrence of each number and their counts. It finds the degree as 2 and then iterates over all numbers with this degree to find the minimal subarray length, which is 2 for number 2.
Approach
Straightforward Solution
A brute-force approach would check every subarray and count frequencies, resulting in O(n^2) or worse time complexity, which is infeasible for large inputs.
Core Observation
The degree of the array is the highest frequency of any element. To find the shortest subarray with the same degree, one must consider the elements that achieve this maximum frequency and find the minimal distance between their first and last occurrences.
Path to Optimal
PreviewThe key insight is to track three pieces of information for each unique element: its frequency count, its first occurrence index, and its last occurrence index…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse three hash maps to track counts, first indices, and last indices of each element while iterating once through the array…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n)
The solution iterates through the array once to build frequency and index maps, then iterates over the unique keys once to find the minimal subarray length, resulting in linear time complexity.
Space
O(n)
Three hash maps store counts and indices for each unique element, which in the worst case can be all elements, leading to O(n) auxiliary space.
Pattern Spotlight
Hash Maps (Frequency Counting with Index Tracking)
When a problem requires frequency-based properties combined with positional constraints, maintain hash maps for counts and first/last occurrences to enable O(1) lookups and a single-pass solution.
Solution
| 1 | class Solution: |
| 2 | def findShortestSubArray(self, nums: list[int]) -> int: |
| 3 | counts = {} |
| 4 | first_index = {} |
| 5 | last_index = {} |
| 6 | |
| 7 | for index, num in enumerate(nums): |
| 8 | counts[num] = counts.get(num, 0) + 1 |
| 9 | |
| 10 | if num not in first_index: |
| 11 | first_index[num] = index |
| 12 | |
| 13 | last_index[num] = index |
| 14 | |
| 15 | degree = max(counts.values()) |
| 16 | min_length = len(nums) |
| 17 | |
| 18 | for num in counts: |
| 19 | if counts[num] == degree: |
| 20 | current_length = last_index[num] - first_index[num] + 1 |
| 21 | min_length = min(min_length, current_length) |
| 22 | |
| 23 | return min_length |
Step-by-Step Solution
Accumulate Frequency and Track First and Last Occurrences
| 3 | counts = {} |
| 4 | first_index = {} |
| 5 | last_index = {} |
| 7 | for index, num in enumerate(nums): |
| 8 | counts[num] = counts.get(num, 0) + 1 |
| 10 | if num not in first_index: |
| 11 | first_index[num] = index |
| 13 | last_index[num] = index |
Objective
To build frequency counts and record the first and last indices of each element in a single pass.
Key Insight
By simultaneously updating counts and recording the first and last positions of each element, the algorithm captures all necessary information to determine the degree and the boundaries of candidate subarrays without additional passes or complex data structures.
Interview Quick-Check
Core Logic
Maintain three hash maps: one for counts, one for first occurrence indices, and one for last occurrence indices, updating them as the array is traversed.
State & Boundaries
Only set the first occurrence index when the element is seen for the first time to preserve the earliest position.
Common Pitfalls & Bugs
Failing to update the last occurrence index on every encounter would lead to incorrect subarray length calculations.
Determine Degree and Initialize Minimal Subarray Length
To find the maximum frequency (degree) of the array and set an initial minimal subarray length for comparison.
Find the Shortest Subarray Matching the Degree
To iterate over elements with frequency equal to the degree and update the minimal subarray length based on their first and last occurrence indices.
Return the Length of the Shortest Subarray with the Same Degree
To return the minimal subarray length found that matches the array's degree.
3 more steps with full analysis available on Pro.
Line Analysis
This solution has 7 Critical lines interviewers watch for.
degree = max(counts.values())Determine the degree of the array as the maximum frequency.
The degree defines the frequency threshold for candidate subarrays and is central to the problem's requirement.
counts[num] = counts.get(num, 0) + 1Increment the frequency count for the current element.
Updating counts on each occurrence builds the frequency distribution needed to find the degree.
first_index[num] = indexRecord the first occurrence index for the current element.
Setting this index only on the first encounter captures the left boundary of the element's subarray.
Full line-by-line criticality + rationale for all 15 lines available on Pro.
Test Your Understanding
Why is it necessary to track both the first and last occurrence indices of elements when computing the shortest subarray with the same degree?
See the answer with Pro.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Degree of an Array from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Degree of an Array drill