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.