697. Degree of an Array
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 54.5%
Problem Breakdown
The problem requires finding the smallest possible length of a contiguous subarray within a given array nums that has the same degree as the original array. The degree of an array is defined as the maximum frequency of any one of its elements.
Inputs:
- A non-empty array of non-negative integers
nums.
Outputs:
- An integer representing the length of the smallest subarray with the same degree as
nums.
Implicit Constraints or Tricky Edge Cases:
- The input array can be large (up to 50,000 elements).
- Elements in the array are between 0 and 49,999.
- The array could have multiple elements with the same maximum frequency.
Intuition
A brute-force approach would involve checking every possible subarray of nums to find one that matches the degree of nums. This approach is inefficient due to its high time complexity (O(n^2)) and space complexity (O(1) for counting frequencies but O(n^2) for storing subarrays).
The key insight is to leverage a dictionary to track the frequency, first occurrence index, and last occurrence index of each element in nums. This allows us to determine the degree of the array and identify the smallest subarray with that degree efficiently.
Approach
-
Initialize a Dictionary:
- Use a dictionary to store three pieces of information for each unique element in
nums:- The frequency of the element.
- The index of its first occurrence.
- The index of its last occurrence.
- Use a dictionary to store three pieces of information for each unique element in
-
Populate the Dictionary:
- Iterate through the array
nums. For each element, update its frequency and record its first and last occurrence indices if it’s being encountered for the first time.
- Iterate through the array
-
Determine the Degree of the Array:
- Find the maximum frequency among all elements in the dictionary.
-
Find the Smallest Subarray with the Same Degree:
- Iterate through the dictionary to find the element(s) with the maximum frequency.
- For each such element, calculate the length of the subarray from its first occurrence index to its last occurrence index.
- Track the minimum length among these subarrays.
-
Return the Result:
- The smallest length found is the answer.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the input array
nums. We make a single pass through the array to populate the dictionary and another pass to determine the smallest subarray. - Space Complexity: O(m), where m is the number of unique elements in
nums. The space required for storing the dictionary.
Solution
def findShortestSubArray(nums):
from collections import defaultdict
# Dictionary to store frequency, first occurrence, and last occurrence of each element
freq_dict = defaultdict(lambda: [0, float('inf'), -float('inf')])
# Populate the dictionary
for i, num in enumerate(nums):
freq_dict[num][0] += 1
if freq_dict[num][1] == float('inf'):
freq_dict[num][1] = i
freq_dict[num][2] = i
# Determine the degree of the array
max_degree = max(freq[0] for freq in freq_dict.values())
# Find the smallest subarray with the same degree
min_length = float('inf')
for freq, first, last in freq_dict.values():
if freq == max_degree:
min_length = min(min_length, last - first + 1)
return min_length
# Example usage:
# nums = [1,2,2,3,1]
# print(findShortestSubArray(nums)) # Output: 2
Edge Cases Handled
- Single Element Array: If the array has only one element, the degree is 1, and the smallest subarray is the array itself.
- All Elements Unique: If all elements are unique, the degree is 1, and the smallest subarray is any single element.
- Multiple Elements with Same Maximum Frequency: The code correctly identifies the smallest subarray among all elements that have the maximum frequency.