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.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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), needing two passes over n elements.
Space Complexity: O(n), primarily due to the need to store index locations.
| 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. |
LeetCode 697. Degree of an Array (Algorithm Explained) • Nick White • 22,787 views views
Watch 9 more video solutions →Practice Degree of an Array with our built-in code editor and test cases.
Practice on FleetCode