# LeetCode 697: Degree of an Array

## Problem Restatement

We are given a non-empty array `nums`.

The degree of an array is the maximum frequency of any element in that array.

We need to find the smallest length of a contiguous subarray that has the same degree as the whole array. If several elements have the maximum frequency, we can choose the one that gives the shortest span. The official statement defines the degree as the maximum frequency of any one element and asks for the shortest contiguous subarray with the same degree.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A non-empty integer array `nums` |
| Output | Length of the shortest contiguous subarray with the same degree |
| Degree | Maximum frequency of any value |
| Subarray | Contiguous part of `nums` |

Example function shape:

```python
def findShortestSubArray(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [1, 2, 2, 3, 1]
```

Frequencies:

| Number | Count |
|---:|---:|
| `1` | `2` |
| `2` | `2` |
| `3` | `1` |

The degree is `2`.

Both `1` and `2` appear twice.

For value `1`, the shortest subarray containing all `1`s is:

```python
[1, 2, 2, 3, 1]
```

Length:

```text
5
```

For value `2`, the shortest subarray containing all `2`s is:

```python
[2, 2]
```

Length:

```text
2
```

Answer:

```python
2
```

Example 2:

```python
nums = [1, 2, 2, 3, 1, 4, 2]
```

Frequencies:

| Number | Count |
|---:|---:|
| `1` | `2` |
| `2` | `3` |
| `3` | `1` |
| `4` | `1` |

The degree is `3`, caused by value `2`.

The first `2` appears at index `1`.

The last `2` appears at index `6`.

So the shortest subarray with degree `3` is:

```python
[2, 2, 3, 1, 4, 2]
```

Length:

```text
6
```

Answer:

```python
6
```

## First Thought: Check Every Subarray

A direct solution is to generate every contiguous subarray and compute its degree.

Then we compare the subarray degree with the original array degree.

Among all matching subarrays, return the shortest length.

This works logically, but it is too slow.

There are `O(n^2)` subarrays, and computing frequencies for each one can cost more time.

We need to use the structure of the degree.

## Key Insight

Suppose the array degree is `d`.

For a subarray to also have degree `d`, it must contain some value exactly `d` times.

Only values that already appear `d` times in the full array can matter.

For such a value `x`, the shortest subarray that contains all occurrences of `x` starts at the first occurrence of `x` and ends at the last occurrence of `x`.

So for every value, we need to know:

| Information | Meaning |
|---|---|
| `count[x]` | How many times `x` appears |
| `first[x]` | First index where `x` appears |
| `last[x]` | Last index where `x` appears |

Then for every value whose count equals the degree, the candidate length is:

```text
last[x] - first[x] + 1
```

The answer is the minimum of these lengths.

## Algorithm

Scan the array once.

For each index `i` and value `x`:

1. If this is the first time seeing `x`, store:
   ```python id="a31i8s"
   first[x] = i
   ```
2. Update:
   ```python id="mndqiw"
   last[x] = i
   count[x] += 1
   ```

After the scan:

1. Compute the degree:
   ```python id="3kyvgm"
   degree = max(count.values())
   ```
2. For every value `x`:
   - if `count[x] == degree`, compute:
     ```python id="owfsdg"
     last[x] - first[x] + 1
     ```
3. Return the minimum candidate length.

## Walkthrough

Consider:

```python
nums = [1, 2, 2, 3, 1, 4, 2]
```

After scanning:

| Value | Count | First | Last |
|---:|---:|---:|---:|
| `1` | `2` | `0` | `4` |
| `2` | `3` | `1` | `6` |
| `3` | `1` | `3` | `3` |
| `4` | `1` | `5` | `5` |

The degree is:

```text
3
```

Only value `2` has count `3`.

Its span length is:

```text
6 - 1 + 1 = 6
```

Return:

```python
6
```

Now consider:

```python
nums = [1, 2, 2, 3, 1]
```

After scanning:

| Value | Count | First | Last | Span length |
|---:|---:|---:|---:|---:|
| `1` | `2` | `0` | `4` | `5` |
| `2` | `2` | `1` | `2` | `2` |
| `3` | `1` | `3` | `3` | `1` |

The degree is `2`.

Values `1` and `2` both match the degree.

Take the shorter span:

```text
min(5, 2) = 2
```

## Correctness

Let the degree of `nums` be `d`.

Any subarray with the same degree must contain some value `x` at least `d` times.

Since no value appears more than `d` times in the full array, `x` must appear exactly `d` times in the full array.

Therefore, `x` is one of the values whose frequency equals the array degree.

For such a value `x`, any subarray containing `x` exactly `d` times must include every occurrence of `x` in the original array.

The shortest contiguous subarray that includes every occurrence of `x` starts at `first[x]` and ends at `last[x]`.

Its length is `last[x] - first[x] + 1`.

The algorithm computes this length for every value whose frequency equals the degree and returns the minimum.

Therefore, it returns the shortest subarray length with the same degree as the original array.

## Complexity

Let `n = len(nums)` and `u` be the number of distinct values.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | We scan the array and then scan distinct values |
| Space | `O(u)` | We store count, first index, and last index for each value |

Since `u <= n`, the space complexity is also `O(n)`.

## Implementation

```python
class Solution:
    def findShortestSubArray(self, nums: list[int]) -> int:
        count = {}
        first = {}
        last = {}

        for i, value in enumerate(nums):
            if value not in first:
                first[value] = i

            last[value] = i
            count[value] = count.get(value, 0) + 1

        degree = max(count.values())
        answer = len(nums)

        for value in count:
            if count[value] == degree:
                length = last[value] - first[value] + 1
                answer = min(answer, length)

        return answer
```

## Code Explanation

We use three hash maps:

```python
count = {}
first = {}
last = {}
```

When a value appears for the first time:

```python
if value not in first:
    first[value] = i
```

we store its first index.

Every time we see the value, we update its last index:

```python
last[value] = i
```

and increment its frequency:

```python
count[value] = count.get(value, 0) + 1
```

The degree is the largest frequency:

```python
degree = max(count.values())
```

Then we inspect every value that reaches this degree:

```python
if count[value] == degree:
```

For that value, the shortest subarray containing all its occurrences is:

```python
length = last[value] - first[value] + 1
```

We keep the smallest such length.

## One-Pass Variant

We can also update the answer during the scan.

Whenever a value reaches a higher degree, reset the answer to its current span.

Whenever a value ties the current degree, minimize the answer.

```python
class Solution:
    def findShortestSubArray(self, nums: list[int]) -> int:
        first = {}
        count = {}

        degree = 0
        answer = 0

        for i, value in enumerate(nums):
            if value not in first:
                first[value] = i

            count[value] = count.get(value, 0) + 1
            span = i - first[value] + 1

            if count[value] > degree:
                degree = count[value]
                answer = span
            elif count[value] == degree:
                answer = min(answer, span)

        return answer
```

This version stores less information because it does not need a separate `last` map.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.findShortestSubArray([1, 2, 2, 3, 1]) == 2
    assert s.findShortestSubArray([1, 2, 2, 3, 1, 4, 2]) == 6

    assert s.findShortestSubArray([1]) == 1
    assert s.findShortestSubArray([1, 1, 1]) == 3
    assert s.findShortestSubArray([1, 2, 3, 4]) == 1
    assert s.findShortestSubArray([1, 2, 2, 3, 3, 3, 2]) == 6
    assert s.findShortestSubArray([2, 1, 1, 2, 1, 3, 3, 3, 1, 3, 1, 3, 2]) == 7

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Expected | Why |
|---|---:|---|
| `[1,2,2,3,1]` | `2` | Standard example |
| `[1,2,2,3,1,4,2]` | `6` | Standard example |
| `[1]` | `1` | Single-element array |
| `[1,1,1]` | `3` | Whole array is required |
| `[1,2,3,4]` | `1` | Degree is `1`, any single element works |
| `[1,2,2,3,3,3,2]` | `6` | Tie-like frequency behavior |
| Longer mixed case | `7` | Checks first and last occurrence spans |