## 697. Degree of an Array

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: [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: [1,2,2,3,1,4,2]
Output: 6
```

Note:

• `nums.length` will be between 1 and 50,000.
• `nums[i]` will be an integer between 0 and 49,999.

• b'
\n\n

#### Approach #1: Left and Right Index [Accepted]

\n

Intuition and Algorithm

\n

An array that has degree `d`, must have some element `x` occur `d` times. If some subarray has the same degree, then some element `x` (that occured `d` times), still occurs `d` times. The shortest such subarray would be from the first occurrence of `x` until the last occurrence.

\n

For each element in the given array, let\'s know `left`, the index of its first occurrence; and `right`, the index of its last occurrence. For example, with `nums = [1,2,3,2,5]` we have `left = 1` and `right = 3`.

\n

Then, for each element `x` that occurs the maximum number of times, `right[x] - left[x] + 1` will be our candidate answer, and we\'ll take the minimum of those candidates.

\n

Python

\n
`class Solution(object):\n    def findShortestSubArray(self, nums):\n        left, right, count = {}, {}, {}\n        for i, x in enumerate(nums):\n            if x not in left: left[x] = i\n            right[x] = i\n            count[x] = count.get(x, 0) + 1\n\n        ans = len(nums)\n        degree = max(count.values())\n        for x in count:\n            if count[x] == degree:\n                ans = min(ans, right[x] - left[x] + 1)\n\n        return ans\n`
\n

Java

\n
`class Solution {\n    public int findShortestSubArray(int[] nums) {\n        Map<Integer, Integer> left = new HashMap(),\n            right = new HashMap(), count = new HashMap();\n\n        for (int i = 0; i < nums.length; i++) {\n            int x = nums[i];\n            if (left.get(x) == null) left.put(x, i);\n            right.put(x, i);\n            count.put(x, count.getOrDefault(x, 0) + 1);\n        }\n\n        int ans = nums.length;\n        int degree = Collections.max(count.values());\n        for (int x: count.keySet()) {\n            if (count.get(x) == degree) {\n                ans = Math.min(ans, right.get(x) - left.get(x) + 1);\n            }\n        }\n        return ans;\n    }\n}\n`
\n

Complexity Analysis

\n
\n
• \n

Time Complexity: , where is the length of `nums`. Every loop is through items with work inside the for-block.

\n
• \n
• \n

Space Complexity: , the space used by `left`, `right`, and `count`.

\n
• \n
\n
\n

Analysis written by: @awice.

\n
'