Code Implementation

class Solution:
    def findShortestSubArray(self, nums):
        from collections import defaultdict
        left, right, count = {}, {}, defaultdict(int)
        for i, x in enumerate(nums):
            if x not in left:
                left[x] = i
            right[x] = i
            count[x] += 1
        degree = max(count.values())
        min_length = len(nums)
        for x in count:
            if count[x] == degree:
                min_length = min(min_length, right[x] - left[x] + 1)
        return min_length
      

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

class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> left = new HashMap<>();
        Map<Integer, Integer> right = new HashMap<>();
        Map<Integer, Integer> count = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            int x = nums[i];
            if (!left.containsKey(x)) left.put(x, i);
            right.put(x, i);
            count.put(x, count.getOrDefault(x, 0) + 1);
        }
        int degree = Collections.max(count.values());
        int minLength = nums.length;
        for (int x : count.keySet()) {
            if (count.get(x) == degree) {
                minLength = Math.min(minLength, right.get(x) - left.get(x) + 1);
            }
        }
        return minLength;
    }
}
      

var findShortestSubArray = function(nums) {
    let left = {}, right = {}, count = {};
    for (let i = 0; i < nums.length; ++i) {
        let x = nums[i];
        if (left[x] === undefined) left[x] = i;
        right[x] = i;
        count[x] = (count[x] || 0) + 1;
    }
    let degree = Math.max(...Object.values(count));
    let minLength = nums.length;
    for (let x in count) {
        if (count[x] === degree) {
            minLength = Math.min(minLength, right[x] - left[x] + 1);
        }
    }
    return minLength;
};
      

Problem Description

Given a non-empty array of non-negative integers called nums, the degree of this array is defined as the maximum frequency of any one of its elements. Your task is to find the smallest possible length of a contiguous subarray of nums that has the same degree as nums itself.

• The input is an array nums of length 1 or more.
• The output is an integer: the length of the shortest subarray with the same degree as nums.
• All elements are non-negative integers.
• There is always at least one valid answer.
• Elements may be reused in the subarray (since it is contiguous), but you cannot skip elements.

Thought Process

To solve this problem, first, we need to understand what the "degree" of the array means. It is the highest number of times any single element occurs in the array. The challenge is to find the shortest possible contiguous subarray (i.e., a sequence of elements in order, without skipping any) that also has this same degree.

A brute-force approach would be to check every possible subarray and compute its degree, but this would be very slow for large arrays. Instead, we can focus on the elements that contribute to the degree and try to find the smallest window that contains all their occurrences.

This leads to a key insight: for each element that occurs as many times as the degree, the shortest subarray covering all its occurrences is the subarray from its first appearance to its last appearance. We just need to find the minimum length among these.

Solution Approach

Here is a step-by-step guide to the optimized algorithm:

1. Count the occurrences: Traverse the array once and keep track of the count of each element using a hash map. This will help us determine the degree of the array.
2. Record first and last positions: For each element, store its first and last occurrence indices in separate hash maps. This will allow us to quickly find the length of the subarray that contains all occurrences of any element.
3. Find the degree: After the traversal, the maximum value in the count map is the degree of the array.
4. Compute minimum subarray length: For each element whose count matches the degree, calculate the length of the subarray from its first to last occurrence. The answer is the minimum such length found.

We use hash maps (dictionaries) because they allow us to store and retrieve counts and positions in constant time, making the algorithm efficient.

Example Walkthrough

Let's walk through a sample input:

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

• Step 1: Count occurrences:
  • 1: 2 times
  • 2: 3 times
  • 3: 1 time
  • 4: 1 time
• Step 2: Record first and last positions:
  • 1: first at 0, last at 4
  • 2: first at 1, last at 6
  • 3: at 3
  • 4: at 5
• Step 3: Degree is 3 (element 2 appears 3 times)
• Step 4: For element 2, the subarray from index 1 to 6 is [2, 2, 3, 1, 4, 2], length = 6.
  No other element has degree 3, so the answer is 6.

Thus, the shortest subarray with the same degree as the whole array is of length 6.

Time and Space Complexity

• Brute-force approach: For each possible subarray, count frequencies (O(n) per subarray), and there are O(n²) subarrays. So, total time is O(n³), which is infeasible for large n.
• Optimized approach: We traverse the array a constant number of times (to fill the maps and to compute the answer), so the time complexity is O(n), where n is the length of nums.
• Space complexity: We use extra hash maps to store counts and positions for each unique element, so space is O(m), where m is the number of unique elements (at most n).

Summary

The key to this problem is recognizing that the shortest subarray with the same degree as the input array must cover all occurrences of at least one element that occurs as often as the degree. By recording the first and last positions of each element and their counts in a single pass, we can efficiently compute the answer in linear time. This approach is both elegant and practical, avoiding unnecessary brute-force checks and leveraging hash maps for fast lookups.