Problem statement

The degree of a non-empty array is the maximum frequency of any one of its elements.

Given a non-negative integer array nums, return 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 degree is 2, reached by both 1 and 2. The 2s span [2,2], length 2, which is shorter than the 1s' span.

Example 2

Input: nums = [1,2,2,3,1,4,2]
Output: 6
Explanation: 2 alone has the maximum frequency, and its first and last occurrences are six apart inclusive.

Example 3

Input: nums = [1]
Output: 1

Constraints

• 1 <= nums.length <= 40
• 0 <= nums[i] <= 40

Hints for Degree of an Array

1. Hint 1

   Any subarray achieving the degree must contain every occurrence of some most-frequent value.

2. Hint 2

   So for each value record its first index, last index and count in one pass.

3. Hint 3

   Among the values whose count equals the degree, the answer is the smallest last - first + 1.

How to solve Degree of an Array

A subarray with the full degree must contain every occurrence of some most-frequent value, so its shortest form runs from that value's first index to its last.

Approach

1. In one pass record first[x], last[x] and count[x].
2. Compute degree = max(count).
3. Return the minimum last[x] - first[x] + 1 over values with count[x] == degree.

Why it works

Any window that omits one occurrence of x has fewer than degree copies of x, so it must instead reach the degree via another value whose span is then what we measure. Taking the minimum span across all maximal-frequency values covers every candidate.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Only values with the full degree count; the span of a lower-frequency value is irrelevant.

Reference solution

Python

def findShortestSubArray(nums):
    first, last, count = {}, {}, {}
    for i, x in enumerate(nums):
        if x not in first:
            first[x] = i
        last[x] = i
        count[x] = count.get(x, 0) + 1
    degree = max(count.values())
    return min(last[x] - first[x] + 1 for x in count if count[x] == degree)

Java

public static int findShortestSubArray(int[] nums) {
    Map<Integer, Integer> first = new HashMap<>();
    Map<Integer, Integer> last = new HashMap<>();
    Map<Integer, Integer> count = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (!first.containsKey(nums[i])) first.put(nums[i], i);
        last.put(nums[i], i);
        count.put(nums[i], count.getOrDefault(nums[i], 0) + 1);
    }
    int degree = 0;
    for (int c : count.values()) degree = Math.max(degree, c);
    int best = nums.length;
    for (Map.Entry<Integer, Integer> e : count.entrySet()) {
        if (e.getValue() == degree) {
            best = Math.min(best, last.get(e.getKey()) - first.get(e.getKey()) + 1);
        }
    }
    return best;
}

C++

int findShortestSubArray(vector<int>& nums) {
    unordered_map<int, int> first, last, count;
    for (int i = 0; i < (int) nums.size(); i++) {
        if (!first.count(nums[i])) first[nums[i]] = i;
        last[nums[i]] = i;
        count[nums[i]]++;
    }
    int degree = 0;
    for (auto& kv : count) degree = max(degree, kv.second);
    int best = (int) nums.size();
    for (auto& kv : count) {
        if (kv.second == degree) best = min(best, last[kv.first] - first[kv.first] + 1);
    }
    return best;
}

JavaScript

var findShortestSubArray = function(nums) {
    const first = new Map(), last = new Map(), count = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (!first.has(nums[i])) first.set(nums[i], i);
        last.set(nums[i], i);
        count.set(nums[i], (count.get(nums[i]) || 0) + 1);
    }
    let degree = 0;
    count.forEach(function(c) { if (c > degree) degree = c; });
    let best = nums.length;
    count.forEach(function(c, value) {
        if (c === degree) {
            const span = last.get(value) - first.get(value) + 1;
            if (span < best) best = span;
        }
    });
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy