Welcome to Subscribe On Youtube

697. Degree of an Array

Level

Easy

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: [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: [1,2,2,3,1,4,2]

Output: 6

Note:

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

Solution

First get each number’s frequency in array nums. Next obtain the numbers with the maximum frequency. Then for each number with the maximum frequency, obtain the first occurrence minIndex and the last occurrence maxIndex of the number, and the subarray with this number has length maxIndex - minIndex + 1. Finally, return the minimum possible length among the subarrays of each number with maximum frequency.

  • public class Degree_of_an_Array {
    
        public static void main(String[] args) {
            Degree_of_an_Array out = new Degree_of_an_Array();
            Solution s = out.new Solution();
    
            System.out.println(s.findShortestSubArray(new int[]{1,2,2,3,1}));
        }
    
        // time: O(N)
        // space: O(N)
        class Solution {
            public int findShortestSubArray(int[] nums) {
    
                if (nums == null || nums.length == 0) {
                    return 0;
                }
    
                Map<Integer, Integer> firstIndex = new HashMap<>();
                Map<Integer, Integer> lastIndex = new HashMap<>();
                Map<Integer, Integer> count = new HashMap<>();
    
                for (int i = 0; i < nums.length; i++) {
                    int x = nums[i];
                    firstIndex.putIfAbsent(x, i); // only update first time
                    lastIndex.put(x, i);
                    count.put(x, count.getOrDefault(x, 0) + 1);
                }
    
                int result = nums.length;
                int degree = Collections.max(count.values());
                for (int x: count.keySet()) {
                    if (count.get(x) == degree) {
                        result = Math.min(result, lastIndex.get(x) - firstIndex.get(x) + 1);
                    }
                }
                return result;
            }
        }
    }
    
    ############
    
    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;
        }
    }
    
  • // OJ: https://leetcode.com/problems/degree-of-an-array/
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
        int findShortestSubArray(vector<int>& nums) {
            unordered_map<int, int> cnt, left, right;
            int deg = 0, ans = INT_MAX;
            for (int i = 0; i < nums.size(); ++i) {
                int n = nums[i];
                cnt[n]++;
                if (cnt[n] > deg) deg = cnt[n];
                if (cnt[n] == 1) left[n] = i;
                right[n] = i;
            }
            for (auto p : cnt) {
                if (p.second != deg) continue;
                ans = min(ans, right[p.first] - left[p.first] + 1);
            }
            return ans;
        }
    };
    
  • 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
    
    ############
    
    import collections
    class Solution(object):
        def findShortestSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if len(nums) == len(set(nums)):
                return 1
            counter = collections.Counter(nums)
            degree_num = counter.most_common(1)[0]
            most_numbers = [num for num in counter if counter[num] == degree_num[1]]
            scale = 100000000
            for most_number in most_numbers:
                appear = [i for i,num in enumerate(nums) if num == most_number]
                appear_scale = max(appear) - min(appear) + 1
                if appear_scale < scale:
                    scale = appear_scale
            return scale
    
  • 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
    }
    
    func min(a, b int) int {
    	if a > b {
    		return b
    	}
    	return a
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    
    
  • class Solution {
        public int findShortestSubArray(int[] nums) {
            Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();
            int maxFrequency = 0;
            for (int num : nums) {
                int frequency = frequencyMap.getOrDefault(num, 0);
                frequency++;
                maxFrequency = Math.max(maxFrequency, frequency);
                frequencyMap.put(num, frequency);
            }
            Set<Integer> maxFrequencySet = new HashSet<Integer>();
            Set<Integer> keySet = frequencyMap.keySet();
            for (int num : keySet) {
                int frequency = frequencyMap.getOrDefault(num, 0);
                if (frequency == maxFrequency)
                    maxFrequencySet.add(num);
            }
            Map<Integer, List<Integer>> numIndicesMap = new HashMap<Integer, List<Integer>>();
            int length = nums.length;
            for (int i = 0; i < length; i++) {
                int num = nums[i];
                if (maxFrequencySet.contains(num)) {
                    List<Integer> indices = numIndicesMap.getOrDefault(num, new ArrayList<Integer>());
                    indices.add(i);
                    numIndicesMap.put(num, indices);
                }
            }
            int minLength = length;
            for (int num : maxFrequencySet) {
                List<Integer> indices = numIndicesMap.getOrDefault(num, new ArrayList<Integer>());
                int size = indices.size();
                if (size > 0) {
                    int minIndex = indices.get(0), maxIndex = indices.get(size - 1);
                    minLength = Math.min(minLength, maxIndex - minIndex + 1);
                }
            }
            return minLength;
        }
    }
    
    ############
    
    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;
        }
    }
    
  • // OJ: https://leetcode.com/problems/degree-of-an-array/
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
        int findShortestSubArray(vector<int>& nums) {
            unordered_map<int, int> cnt, left, right;
            int deg = 0, ans = INT_MAX;
            for (int i = 0; i < nums.size(); ++i) {
                int n = nums[i];
                cnt[n]++;
                if (cnt[n] > deg) deg = cnt[n];
                if (cnt[n] == 1) left[n] = i;
                right[n] = i;
            }
            for (auto p : cnt) {
                if (p.second != deg) continue;
                ans = min(ans, right[p.first] - left[p.first] + 1);
            }
            return ans;
        }
    };
    
  • 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
    
    ############
    
    import collections
    class Solution(object):
        def findShortestSubArray(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if len(nums) == len(set(nums)):
                return 1
            counter = collections.Counter(nums)
            degree_num = counter.most_common(1)[0]
            most_numbers = [num for num in counter if counter[num] == degree_num[1]]
            scale = 100000000
            for most_number in most_numbers:
                appear = [i for i,num in enumerate(nums) if num == most_number]
                appear_scale = max(appear) - min(appear) + 1
                if appear_scale < scale:
                    scale = appear_scale
            return scale
    
  • 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
    }
    
    func min(a, b int) int {
    	if a > b {
    		return b
    	}
    	return a
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    
    

All Problems

All Solutions