1. Degree of an Array (LeetCode)
Model answer
The task
Given an integer array, find the length of its shortest contiguous subarray whose elements have the same degree as the full array. The degree is the highest frequency of any value in the array.
Key idea
For each value, record its frequency and the indices of its first and last occurrences. A value’s shortest covering subarray spans those two indices; among values with maximum frequency, return the smallest such span.
Approach
- Scan the array once, recording each value’s count, first index, and last index.
- Track the largest count seen, which is the array’s degree.
- For every value with that count, calculate
last - first + 1. - Return the minimum calculated length.
from typing import List
class Solution:
def findShortestSubArray(self, nums: List[int]) -> int:
counts = {}
first = {}
last = {}
for i, value in enumerate(nums):
if value not in counts:
counts[value] = 0
first[value] = i
counts[value] += 1
last[value] = i
degree = max(counts.values())
shortest = len(nums)
for value, count in counts.items():
if count == degree:
span = last[value] - first[value] + 1
shortest = min(shortest, span)
return shortest
Complexity:
- Time: O(n), for scanning the array and checking the distinct values.
- Space: O(k), where
kis the number of distinct values stored in the dictionaries.
Common follow-ups
- How would you return the actual subarray as well as its length? Keep the start and end indices of the best span.
- What if the array is empty? Define the expected behavior, such as returning
0, and handle it before callingmax. - Can the result be found in one pass? Yes; update each value’s span and count while tracking the best span for the current degree.