Skip to content

697. Degree of an Array

Description

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.

 

Example 1:

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:

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.

Solutions

Solution 1

Thinking

The degree is the maximum frequency. A shortest subarray with the same degree must cover the first and last occurrence of some mode.

Count frequencies and record endpoints. For values that attain the degree, take the minimum \(right-left+1\).

 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 = Counter(nums)
        degree = cnt.most_common()[0][1]
        left, right = {}, {}
        for i, v in enumerate(nums):
            if v not in left:
                left[v] = i
            right[v] = i
        ans = inf
        for v in nums:
            if cnt[v] == degree:
                t = right[v] - left[v] + 1
                if ans > t:
                    ans = t
        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
class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        Map<Integer, Integer> left = new HashMap<>();
        Map<Integer, Integer> right = new HashMap<>();
        int degree = 0;
        for (int i = 0; i < nums.length; ++i) {
            int v = nums[i];
            cnt.put(v, cnt.getOrDefault(v, 0) + 1);
            degree = Math.max(degree, cnt.get(v));
            if (!left.containsKey(v)) {
                left.put(v, i);
            }
            right.put(v, i);
        }
        int ans = 1000000;
        for (int v : nums) {
            if (cnt.get(v) == degree) {
                int t = right.get(v) - left.get(v) + 1;
                if (ans > t) {
                    ans = t;
                }
            }
        }
        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
class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        unordered_map<int, int> cnt;
        unordered_map<int, int> left;
        unordered_map<int, int> right;
        int degree = 0;
        for (int i = 0; i < nums.size(); ++i) {
            int v = nums[i];
            degree = max(degree, ++cnt[v]);
            if (!left.count(v)) {
                left[v] = i;
            }
            right[v] = i;
        }
        int ans = 1e6;
        for (int v : nums) {
            if (cnt[v] == degree) {
                int t = right[v] - left[v] + 1;
                if (ans > t) {
                    ans = t;
                }
            }
        }
        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
func findShortestSubArray(nums []int) int {
    cnt := map[int]int{}
    left := map[int]int{}
    right := map[int]int{}
    var degree int
    for i, v := range nums {
        cnt[v]++
        if degree < cnt[v] {
            degree = cnt[v]
        }
        if _, ok := left[v]; !ok {
            left[v] = i
        }
        right[v] = i
    }
    ans := 100000
    for v, c := range cnt {
        if c == degree {
            t := right[v] - left[v] + 1
            if ans > t {
                ans = t
            }
        }
    }
    return ans
}

Solution 2

Thinking

Method 1 records endpoints in one pass. We can also collect the modes first and scan first/last indices per mode. The helpers are longer, the complexity is the same.

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
func findShortestSubArray(nums []int) (ans int) {
    ans = 50000
    numsMap := make(map[int]int, len(nums))
    for _, num := range nums {
        numsMap[num]++
    }
    var maxDegree int
    for _, num := range numsMap {
        maxDegree = max(num, maxDegree)
    }
    degreeNums := getMaxDegreeElem(maxDegree, numsMap)
    for _, num := range degreeNums {
        f := findSubArray(num, nums)
        ans = min(ans, f)
    }
    return
}

func findSubArray(target int, nums []int) int {
    start := getStartIdx(target, nums)
    end := getEndIdx(target, nums)
    return (end - start) + 1
}

func getStartIdx(target int, nums []int) (start int) {
    for idx, num := range nums {
        if num == target {
            start = idx
            break
        }
    }
    return start
}

func getEndIdx(target int, nums []int) (end int) {
    for i := len(nums) - 1; i > 0; i-- {
        if nums[i] == target {
            end = i
            break
        }
    }
    return
}

func getMaxDegreeElem(maxDegree int, numsMap map[int]int) []int {
    var ans []int
    for key, value := range numsMap {
        if value == maxDegree {
            ans = append(ans, key)
        }
    }
    return ans
}

Comments