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
}

697 - Degree of an Array

697. Degree of an Array

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

697. Degree of an Array

Level

Description

Solution

All Problems

All Solutions