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

 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

 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