Problem

Given a non-empty array of non-negative integers 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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


    
    
    Input: nums = [1,2,2,3,1]
    Output: 2
    Explanation: 
    The input array has a degree of 2 because both elements 1 and 2 appear twice.
    Of the subarrays that have the same degree:
    [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
    The shortest length is 2. So return 2.

Example 2

1
2
3
4
5
6
7
8
9


    
    
    Input: nums = [1,2,2,3,1,4,2]
    Output: 6
    Explanation: 
    The degree is 3 because the element 2 is repeated 3 times.
    So [2,2,3,1,4,2] is the shortest subarray, therefore returning 6.

Constraints

  • nums.length will be between 1 and 50,000.
  • nums[i] will be an integer between 0 and 49,999.

Solution

Method 1 – Hash Map for First/Last Occurrence and Frequency

Intuition

To find the shortest subarray with the same degree as the original array, we need to know the frequency (degree) of each element and the first and last positions where each element appears. The answer is the minimum length among all elements with maximum frequency.

Approach

  1. Use a hash map to record the frequency of each number.
  2. Use two hash maps to record the first and last occurrence index of each number.
  3. Find the degree (maximum frequency) of the array.
  4. For each number with frequency equal to the degree, compute the length of its subarray (last - first + 1).
  5. Return the minimum such length.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        unordered_map<int, int> cnt, first, last;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            int x = nums[i];
            cnt[x]++;
            if (!first.count(x)) first[x] = i;
            last[x] = i;
        }
        int deg = 0, ans = n;
        for (auto& [k, v] : cnt) deg = max(deg, v);
        for (auto& [k, v] : cnt) {
            if (v == deg) ans = min(ans, last[k] - first[k] + 1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func findShortestSubArray(nums []int) int {
    cnt := map[int]int{}
    first := map[int]int{}
    last := map[int]int{}
    for i, x := range nums {
        cnt[x]++
        if _, ok := first[x]; !ok {
            first[x] = i
        }
        last[x] = i
    }
    deg, ans := 0, len(nums)
    for _, v := range cnt {
        if v > deg {
            deg = v
        }
    }
    for k, v := range cnt {
        if v == deg {
            l := last[k] - first[k] + 1
            if l < ans {
                ans = l
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        Map<Integer, Integer> first = new HashMap<>();
        Map<Integer, Integer> last = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            cnt.put(x, cnt.getOrDefault(x, 0) + 1);
            if (!first.containsKey(x)) first.put(x, i);
            last.put(x, i);
        }
        int deg = 0, ans = n;
        for (int v : cnt.values()) deg = Math.max(deg, v);
        for (int k : cnt.keySet()) {
            if (cnt.get(k) == deg) {
                ans = Math.min(ans, last.get(k) - first.get(k) + 1);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun findShortestSubArray(nums: IntArray): Int {
        val cnt = mutableMapOf<Int, Int>()
        val first = mutableMapOf<Int, Int>()
        val last = mutableMapOf<Int, Int>()
        for ((i, x) in nums.withIndex()) {
            cnt[x] = cnt.getOrDefault(x, 0) + 1
            if (x !in first) first[x] = i
            last[x] = i
        }
        val deg = cnt.values.maxOrNull() ?: 0
        var ans = nums.size
        for ((k, v) in cnt) {
            if (v == deg) {
                ans = minOf(ans, last[k]!! - first[k]!! + 1)
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def findShortestSubArray(self, nums: list[int]) -> int:
        cnt: dict[int, int] = {}
        first: dict[int, int] = {}
        last: dict[int, int] = {}
        for i, x in enumerate(nums):
            cnt[x] = cnt.get(x, 0) + 1
            if x not in first:
                first[x] = i
            last[x] = i
        deg: int = max(cnt.values())
        ans: int = len(nums)
        for x in cnt:
            if cnt[x] == deg:
                ans = min(ans, last[x] - first[x] + 1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn find_shortest_sub_array(nums: Vec<i32>) -> i32 {
        use std::collections::HashMap;
        let mut cnt = HashMap::new();
        let mut first = HashMap::new();
        let mut last = HashMap::new();
        for (i, &x) in nums.iter().enumerate() {
            *cnt.entry(x).or_insert(0) += 1;
            first.entry(x).or_insert(i);
            last.insert(x, i);
        }
        let deg = *cnt.values().max().unwrap();
        let mut ans = nums.len();
        for (&k, &v) in &cnt {
            if v == deg {
                ans = ans.min(last[&k] - first[&k] + 1);
            }
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    findShortestSubArray(nums: number[]): number {
        const cnt = new Map<number, number>();
        const first = new Map<number, number>();
        const last = new Map<number, number>();
        for (let i = 0; i < nums.length; i++) {
            const x = nums[i];
            cnt.set(x, (cnt.get(x) ?? 0) + 1);
            if (!first.has(x)) first.set(x, i);
            last.set(x, i);
        }
        const deg = Math.max(...cnt.values());
        let ans = nums.length;
        for (const [k, v] of cnt.entries()) {
            if (v === deg) {
                ans = Math.min(ans, last.get(k)! - first.get(k)! + 1);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the array, since we scan the array a constant number of times.
  • 🧺 Space complexity: O(n), for the hash maps.