# Degree of an Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/degree-of-an-array)
Canonical: https://scaleengineer.com/dsa/problems/degree-of-an-array
**Data structures:** Array, Hash Table
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [Expedia](https://scaleengineer.com/companies/expedia), [IBM](https://scaleengineer.com/companies/ibm), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [PayPal](https://scaleengineer.com/companies/paypal), [SoFi](https://scaleengineer.com/companies/sofi), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [ZScaler](https://scaleengineer.com/companies/zscaler), [Salesforce](https://scaleengineer.com/companies/salesforce), [Turing](https://scaleengineer.com/companies/turing), [Rivian](https://scaleengineer.com/companies/rivian), [Paycom](https://scaleengineer.com/companies/paycom), [GE Digital](https://scaleengineer.com/companies/ge-digital)
---
## Problem
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.

# Approaches
## Two-Pass Approach with Hash Maps
This approach involves two separate traversals. The first pass gathers information about each number: its frequency, and the indices of its first and last occurrences. The second pass uses this information to determine the degree of the array and then finds the shortest subarray length among all elements that have this degree.
**Time:** O(N), where N is the number of elements in the array. The first pass takes O(N) to populate the maps. The second pass involves finding the degree (O(U), where U is the number of unique elements) and then iterating through the unique elements again (O(U)). Since U <= N, the total time complexity is O(N). · **Space:** O(U), where U is the number of unique elements in the array. In the worst case, all elements are unique, so the space complexity is O(N). This space is used to store the three hash maps.
**Pros:** Conceptually simple and easy to follow the logic.; Correctly solves the problem within the given constraints.
**Cons:** Requires two passes over the data (one over the array, one over the map keys), which is less efficient than a single-pass solution.; Uses more memory due to three separate hash maps, although the asymptotic complexity is the same as other map-based approaches.
### Explanation
The core idea is that the shortest subarray with the same degree as the original array must span from the first to the last occurrence of an element that has the maximum frequency. The length of this subarray is `last_index - first_index + 1`. We can find the minimum of these lengths over all elements that have the maximum frequency (the degree).

**Step 1: Information Gathering (First Pass)**
We iterate through `nums` once to populate three HashMaps:
- `count`: Stores the frequency of each number.
- `first`: Stores the index of the first occurrence of each number.
- `last`: Stores the index of the last occurrence of each number.

```java
Map<Integer, Integer> count = new HashMap<>();
Map<Integer, Integer> first = new HashMap<>();
Map<Integer, Integer> last = new HashMap<>();

for (int i = 0; i < nums.length; i++) {
    int num = nums[i];
    count.put(num, count.getOrDefault(num, 0) + 1);
    if (!first.containsKey(num)) {
        first.put(num, i);
    }
    last.put(num, i);
}
```

**Step 2: Finding the Shortest Subarray (Second Pass)**
After populating the maps, we first determine the `degree` of the array by finding the maximum frequency in the `count` map. Then, we iterate through the elements that have this `degree` and calculate the length of their corresponding subarrays. We keep track of the minimum length found.

```java
int degree = 0;
for (int freq : count.values()) {
    degree = Math.max(degree, freq);
}

int minLength = nums.length;
for (int num : count.keySet()) {
    if (count.get(num) == degree) {
        minLength = Math.min(minLength, last.get(num) - first.get(num) + 1);
    }
}

return minLength;
```
### Algorithm
- Initialize three HashMaps: `count` to store frequencies, `first` to store the first index, and `last` to store the last index of each number.
- Iterate through the input array `nums` from left to right with index `i`.
- For each element `num = nums[i]`, update its information in the three maps: increment its frequency in `count`, record its first occurrence index in `first` if it's not already present, and always update its last occurrence index in `last`.
- After the first pass, calculate the `degree` of the array by finding the maximum frequency in the `count` map.
- Initialize `minLength` to `nums.length`.
- Iterate through the unique numbers (the keys of the `count` map).
- If a number's frequency equals the `degree`, calculate the length of its span: `len = last.get(num) - first.get(num) + 1`.
- Update `minLength = Math.min(minLength, len)`.
- Finally, return `minLength`.

## One-Pass Approach with Hash Maps
This is an optimized approach that finds the solution in a single pass through the array. It maintains the count and first occurrence index of each number as it iterates. By tracking the current degree and the corresponding minimum length on the fly, it avoids a second pass, making it more efficient.
**Time:** O(N), where N is the number of elements in the array. We iterate through the array only once. Each hash map operation takes, on average, O(1) time. · **Space:** O(U), where U is the number of unique elements in the array. In the worst case, where all elements are unique, the space complexity is O(N). This space is for the `count` and `first` hash maps.
**Pros:** Most efficient solution with optimal O(N) time complexity.; Processes the array in a single pass, which is memory and cache-friendly.
**Cons:** The logic is slightly more complex to reason about compared to the two-pass approach as updates happen dynamically.
### Explanation
We can compute the result dynamically in a single pass. As we iterate through the array, we update the count of the current element. Each time a count is updated, we check if it affects the overall degree and the minimum length. If the current element's frequency becomes the new degree, we update the minimum length. If its frequency matches the current degree, we check if it provides a shorter subarray.

**Algorithm Steps:**
1. Initialize a `count` map for frequencies, a `first` map for first indices, `degree = 0`, and `minLength = 0`.
2. Iterate through the array `nums` with index `i`.
3. For each element `num`, record its first index if not seen before and update its count.
4. Check the new count:
   - If `count(num) > degree`, we have a new highest frequency. Update `degree` and set `minLength` to the length of the current element's span (`i - first.get(num) + 1`).
   - If `count(num) == degree`, we have another element with the same max frequency. Update `minLength` to the minimum of its current value and the new span's length.

```java
class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        Map<Integer, Integer> first = new HashMap<>();
        int degree = 0;
        int minLength = 0;

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            first.putIfAbsent(num, i);
            count.put(num, count.getOrDefault(num, 0) + 1);
            
            int currentCount = count.get(num);
            if (currentCount > degree) {
                degree = currentCount;
                minLength = i - first.get(num) + 1;
            } else if (currentCount == degree) {
                minLength = Math.min(minLength, i - first.get(num) + 1);
            }
        }
        return minLength;
    }
}
```
### Algorithm
- Initialize two HashMaps: `count` (for frequencies) and `first` (for first indices).
- Initialize two integers: `degree = 0` and `minLength = 0`.
- Iterate through the input array `nums` from left to right with index `i`.
- For each element `num`, store its first occurrence index in `first` (if not already present) and increment its count in `count`.
- Let `currentCount` be the new count of `num`.
- If `currentCount > degree`, update `degree` to `currentCount` and `minLength` to the current span length (`i - first.get(num) + 1`).
- Else if `currentCount == degree`, update `minLength` with the minimum of the current `minLength` and the current span length.
- After the loop, return `minLength`.

# Solutions
### Java

```java
class Solution { public int findShortestSubArray ( int [] nums ) { Map < Integer , Integer > cnt = new HashMap <>(); Map < Integer , Integer > left = new HashMap <>(); Map < Integer , Integer > right = new HashMap <>(); int degree = 0 ; for ( int i = 0 ; i < nums . length ; ++ i ) { int v = nums [ i ]; cnt . put ( v , cnt . getOrDefault ( v , 0 ) + 1 ); degree = Math . max ( degree , cnt . get ( v )); if (! left . containsKey ( v )) { left . put ( v , i ); } right . put ( v , i ); } int ans = 1000000 ; for ( int v : nums ) { if ( cnt . get ( v ) == degree ) { int t = right . get ( v ) - left . get ( v ) + 1 ; if ( ans > t ) { ans = t ; } } } return ans ; } }
```

### CPP

```cpp
class Solution { public: int findShortestSubArray ( vector < int >& nums ) { unordered_map < int , int > cnt ; unordered_map < int , int > left ; unordered_map < int , int > right ; int degree = 0 ; for ( int i = 0 ; i < nums . size (); ++ i ) { int v = nums [ i ]; degree = max ( degree , ++ cnt [ v ]); if ( ! left . count ( v )) { left [ v ] = i ; } right [ v ] = i ; } int ans = 1e6 ; for ( int v : nums ) { if ( cnt [ v ] == degree ) { int t = right [ v ] - left [ v ] + 1 ; if ( ans > t ) { ans = t ; } } } return ans ; } };
```

### Python

```python
class Solution : def findShortestSubArray ( self , nums : List [ int ]) -> int : cnt = Counter ( nums ) degree = cnt . most_common ()[ 0 ][ 1 ] left , right = {}, {} for i , v in enumerate ( nums ): if v not in left : left [ v ] = i right [ v ] = i ans = inf for v in nums : if cnt [ v ] == degree : t = right [ v ] - left [ v ] + 1 if ans > t : ans = t return ans
```