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

Example function shape:

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

Examples

Example 1:

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

Frequencies:

The degree is 2.

Both 1 and 2 appear twice.

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

[1, 2, 2, 3, 1]

Length:

5

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

[2, 2]

Length:

2

Answer:

2

Example 2:

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

Frequencies:

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:

[2, 2, 3, 1, 4, 2]

Length:

6

Answer:

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:

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

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:

   first[x] = i
2. Update:

   last[x] = i
   count[x] += 1

After the scan:

1. Compute the degree:

   degree = max(count.values())
2. For every value x:
   • if count[x] == degree, compute:

     last[x] - first[x] + 1
3. Return the minimum candidate length.

Walkthrough

Consider:

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

After scanning:

The degree is:

3

Only value 2 has count 3.

Its span length is:

6 - 1 + 1 = 6

Return:

6

Now consider:

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

After scanning:

The degree is 2.

Values 1 and 2 both match the degree.

Take the shorter span:

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.

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

Implementation

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:

count = {}
first = {}
last = {}

When a value appears for the first time:

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

we store its first index.

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

last[value] = i

and increment its frequency:

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

The degree is the largest frequency:

degree = max(count.values())

Then we inspect every value that reaches this degree:

if count[value] == degree:

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

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.

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

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: