Algorithm
Problem Name: 697. Degree of an Array
Problem Link: https://leetcode.com/problems/degree-of-an-array/
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.lengthwill be between 1 and 50,000.nums[i]will be an integer between 0 and 49,999.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int findShortestSubArray(vector<int>& nums) {
unordered_map < int, int>idx, cnt;
int degree = 0, minlen = nums.size();
for(int i = 0; i < nums.size(); i++){
if(!idx.count(nums[i])) idx[nums[i]] = i;
if(++cnt[nums[i]] == degree) minlen = min(minlen, i - idx[nums[i]] + 1);
if(cnt[nums[i]] > degree){
degree = cnt[nums[i]];
minlen = i - idx[nums[i]] + 1;
}
}
return minlen;
}
};
Input
nums = [1,2,2,3,1]
Output
2
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int findShortestSubArray(int[] nums) {
Map map = new HashMap<>();
int maxCount = 0;
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
maxCount = Math.max(maxCount, map.get(num));
}
int start = 0;
int end = 0;
map.clear();
int minLength = Integer.MAX_VALUE;
while (end < nums.length) {
map.put(nums[end], map.getOrDefault(nums[end], 0) + 1);
while (start <= end && map.get(nums[end]) == maxCount) {
minLength = Math.min(minLength, end - start + 1);
map.put(nums[start], map.get(nums[start]) - 1);
start++;
}
end++;
}
return minLength;
}
}
Input
nums = [1,2,2,3,1]
Output
2
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const findShortestSubArray = function(nums) {
const left = {};
const right = {};
const count = {};
for (let i = 0; i < nums.length; i++) {
if (!left.hasOwnProperty(nums[i])) {
left[nums[i]] = i;
}
right[nums[i]] = i;
count[nums[i]] = count[nums[i]] ? count[nums[i]] + 1 : 1;
}
const degree = Math.max(...Object.keys(count).map(el => count[el]));
let res = nums.length;
for (let el in count) {
if (count.hasOwnProperty(el) && count[el] === degree) {
res = Math.min(res, right[el] - left[el] + 1);
}
}
return res;
};
Input
nums = [1,2,2,3,1,4,2]
Output
6
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findShortestSubArray(self, nums):
cnt, seen = collections.Counter(nums), collections.defaultdict(list)
degree = max(cnt.values())
for i, v in enumerate(nums): seen[v].append(i)
return min(seen[v][-1] - seen[v][0] + 1 for v in cnt if cnt[v] == degree)
Input
nums = [1,2,2,3,1,4,2]
Output
6
#5 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
using System.Linq;
namespace LeetCode
{
public class _0697_DegreeOfAnArray
{
public int FindShortestSubArray(int[] nums)
{
var counts = new Dictionary < int, int>();
var left = new Dictionary<int, int>();
var right = new Dictionary < int, int>();
for (int i = 0; i < nums.Length; i++)
{
if (!left.ContainsKey(nums[i]))
left[nums[i]] = i;
right[nums[i]] = i;
if (!counts.ContainsKey(nums[i]))
counts[nums[i]] = 1;
else
counts[nums[i]]++;
}
var max = counts.Values.Max();
var answer = nums.Length;
foreach (var key in counts.Keys)
{
if (counts[key] == max)
{
answer = Math.Min(answer, right[key] - left[key] + 1);
}
}
return answer;
}
}
}
Input
nums = [1,2,2,3,1]
Output
2