Leetcode 697. Degree of an Array
Problem Explanation
In this problem, we are given a non-empty array of non-negative integers. The degree of an array is defined as the maximum frequency of any of its elements.
Our task is to find the smallest possible length of a contiguous subarray of the given array, which shares the same degree as the original array.
For instance, consider the following example.
1 2 3Example 4 5Input: [1, 2, 2, 3, 1] 6Output: 2 7 8The 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.
Approach
To solve this problem, we use two hash maps. One(debut
) to store the first time an element appears in the array, and the other(count
) to keep the count of each number.
We iterate the array, If the element is first-time appearing, update the debut
map with the current index, also update the count
map incrementing the count of the element.
If the count of the element is greater than the current degree
, then update the degree
and calculate the new length of the subarray.
If the count becomes equal to the degree
, then we know we found another element with the same degree, hence, we update our answer with minimum
of current answer and the new length of subarray.
Finally, return the minimum length of the subarray.
Complexity Analysis
The time complexity for this algorithm is O(n), based on a single traversal of the array.
The space complexity for this algorithm is also O(n), where n is the size of the array. This space is used to store the indexes and counts of elements in the hash maps.
As an example, let's walk through the approach for example 1.
In the first step, we meet 1 and 2. We add them into both debut
and count
, and the degree will be updated to 1.
In the second step, we meet another 2, now the count of 2 becomes 2, which is greater than the degree, thus the degree will be updated to 2, and the answer will become its length which is 2(1 - 0 + 1).
In the third and fourth step, the degree will not be updated.
In the final step, we meet another 1, it has the same count with 2 which is 2, thus we update the answer with the minimum
of the current answer and its length which is 4(4 - 0 + 1), so the final answer is 2.
Solution
C++ Solution
Here is the C++ solution for the problem.
1 2cpp 3class Solution { 4public: 5 int findShortestSubArray(vector<int>& nums) { 6 int ans = 0; 7 int degree = 0; 8 unordered_map<int, int> debut; 9 unordered_map<int, int> count; 10 11 for (int i = 0; i < nums.size(); ++i) { 12 if (!debut.count(nums[i])) 13 debut[nums[i]] = i; 14 if (++count[nums[i]] > degree) { 15 degree = count[nums[i]]; 16 ans = i - debut[nums[i]] + 1; 17 } else if (count[nums[i]] == degree) { 18 ans = min(ans, i - debut[nums[i]] + 1); 19 } 20 } 21 22 return ans; 23 } 24};
Python Solution
Here is the equivalent Python solution for the problem.
1 2python 3class Solution: 4 def findShortestSubArray(self, nums): 5 debut = {} 6 count = {} 7 ans = 0 8 degree = 0 9 10 for i, num in enumerate(nums): 11 if num not in debut: 12 debut[num] = i 13 count[num] = count.get(num, 0) + 1 14 15 if count[num] > degree: 16 degree = count[num] 17 ans = i - debut[num] + 1 18 elif count[num] == degree: 19 ans = min(ans, i - debut[num] + 1) 20 21 return ans
In both solutions above, we are using the unordered map in C++ or dictionary in Python to keep track of the first appearance of each number (i.e., 'debut'), as well as the frequency of each number (i.e., 'count'). While traversing the array, we compare the frequency of the current number with the max degree 'degree', if they are the same, we update our answer.## JavaScript Solution
Here is the equivalent JavaScript solution for the problem.
1 2javascript 3var findShortestSubArray = function(nums) { 4 let debut = {}; 5 let count = {}; 6 let ans = 0; 7 let degree = 0; 8 9 for (let i = 0; i < nums.length; ++i) { 10 if (!debut.hasOwnProperty(nums[i])) { 11 debut[nums[i]] = i; 12 } 13 if (!count.hasOwnProperty(nums[i])) { 14 count[nums[i]] = 1; 15 } else { 16 count[nums[i]] += 1; 17 } 18 19 if (count[nums[i]] > degree) { 20 degree = count[nums[i]]; 21 ans = i - debut[nums[i]] + 1; 22 } else if (count[nums[i]] == degree) { 23 ans = Math.min(ans, i - debut[nums[i]] + 1); 24 } 25 } 26 27 return ans; 28};
Java Solution
And here is the equivalent Java solution for the problem.
1
2java
3class Solution {
4 public int findShortestSubArray(int[] nums) {
5 HashMap<Integer, Integer> debut = new HashMap<>();
6 HashMap<Integer, Integer> count = new HashMap<>();
7 int degree = 0, ans = 0;
8
9 for (int i = 0; i < nums.length; ++i) {
10 if (!debut.containsKey(nums[i])) {
11 debut.put(nums[i], i);
12 }
13 count.put(nums[i], count.getOrDefault(nums[i], 0) + 1);
14
15 if (count.get(nums[i]) > degree) {
16 degree = count.get(nums[i]);
17 ans = i - debut.get(nums[i]) + 1;
18 } else if (count.get(nums[i]) == degree) {
19 ans = Math.min(ans, i - debut.get(nums[i]) + 1);
20 }
21 }
22
23 return ans;
24 }
25}
In both solutions above (JavaScript and Java), we use a similar approach as in the Python and C++ solutions. We maintain two hashmaps (or objects in the case of JavaScript), debut
to store the first occurrence of each number and count
to keep track of frequency for each number. While traversing the array, if we find an element with frequency equal to the degree
, we update the minimum length.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.