Degree of an Array

Problem

The degree of an array is the maximum frequency of any one of its elements. Find the length of the smallest contiguous subarray that has the same degree as the whole array.

Constraints

• 1 ≤ nums.length ≤ 5·10⁴
• 0 ≤ nums[i] < 5·10⁴

Approach — Hashing & Counting

This is a Hashing & Counting problem. The idea: store what you've seen in a hash map for O(1) lookups, trading a little space to avoid a nested scan. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def findShortestSubArray(self, 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
        deg = max(count.values())
        return min(last[x] - first[x] + 1 for x in count if count[x] == deg)

Java

class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> first = new HashMap<>(), count = new HashMap<>();
        int degree = 0, res = 0;
        for (int i = 0; i < nums.length; i++) {
            int n = nums[i];
            first.putIfAbsent(n, i);
            int c = count.merge(n, 1, Integer::sum);
            if (c > degree) { degree = c; res = i - first.get(n) + 1; }
            else if (c == degree) res = Math.min(res, i - first.get(n) + 1);
        }
        return res;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.