Degree of an Array

easy array hash map

Problem

Given a non-empty array of non-negative integers, the degree of the array is the maximum frequency of any element. Find the smallest possible length of a contiguous subarray that has the same degree.

Inputnums = [1, 2, 2, 3, 1]

Output2

Degree is 2 (both 1 and 2). Shortest range with degree 2 is [2, 2] (length 2).

nums (comma-separated)

def find_shortest_subarray(nums):
    first, count = {}, {}
    degree, ans = 0, len(nums)
    for i, v in enumerate(nums):
        first.setdefault(v, i)
        count[v] = count.get(v, 0) + 1
        if count[v] > degree:
            degree = count[v]
            ans = i - first[v] + 1
        elif count[v] == degree:
            ans = min(ans, i - first[v] + 1)
    return ans

function findShortestSubArray(nums) {
  const first = new Map(), count = new Map();
  let degree = 0, ans = nums.length;
  for (let i = 0; i < nums.length; i++) {
    const v = nums[i];
    if (!first.has(v)) first.set(v, i);
    count.set(v, (count.get(v) || 0) + 1);
    if (count.get(v) > degree) { degree = count.get(v); ans = i - first.get(v) + 1; }
    else if (count.get(v) === degree) ans = Math.min(ans, i - first.get(v) + 1);
  }
  return ans;
}

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

int findShortestSubArray(vector<int>& nums) {
    unordered_map<int, int> first, count;
    int degree = 0, ans = nums.size();
    for (int i = 0; i < (int)nums.size(); i++) {
        int v = nums[i];
        if (!first.count(v)) first[v] = i;
        count[v]++;
        if (count[v] > degree) { degree = count[v]; ans = i - first[v] + 1; }
        else if (count[v] == degree) ans = min(ans, i - first[v] + 1);
    }
    return ans;
}

Explanation

The "degree" is the highest frequency of any value. We need the shortest contiguous chunk that still has that same degree. The key realization: for any value, the shortest span containing all of its copies runs from its first occurrence to its last.

So we track three things as we scan: first (a hash map of each value's first index), count (its running frequency), and the current best window length ans.

For each value v at index i, when its count exceeds the current degree we have a new most-frequent value, so we update the degree and set ans = i - first[v] + 1. When its count ties the degree, it could give a shorter span, so we take the minimum.

Example: nums = [1, 2, 2, 3, 1]. Both 1 and 2 appear twice (degree 2). The 2s span indices 1 to 2 (length 2), while the 1s span 0 to 4 (length 5). The shortest is 2.

Everything is computed in a single pass with constant-time map operations, so it is linear time.

Time: O(n) Space: O(n)