Degree of an Array
On this page 
Problem Statement Solution 1: Brute Force Approach Solution 2: Hash Map for Frequency and Indices Solution 3: Two-Pass Approach Approach Solution 4: Sliding Window Approach Solution 5: Using Map and Array Solution 6: Optimized Frequency Count Solution 7: Using Object.entries() More Problems Solutions
Problem Statement
In this problem, you are given a non-empty array of non-negative integers, nums. The degree of an array is defined as the maximum frequency of any single element within the array. Your task is to determine the smallest possible length of a contiguous subarray that has the same degree as the original array.
Example 1
Input: nums = [1, 2, 2, 3, 1]
Output: 2
Example 2
Input: nums = [1, 2, 2, 3, 1, 4, 2]
Output: 6
Solution 1: Brute Force Approach
function findSmallestLengthBruteForce(nums) {
const degree = Math.max(...nums.map(n => nums.filter(x => x === n).length));
let minLength = nums.length;
for (let start = 0; start < nums.length; start++) {
for (let end = start; end < nums.length; end++) {
const subArray = nums.slice(start, end + 1);
const subDegree = Math.max(...subArray.map(n => subArray.filter(x => x === n).length));
if (subDegree === degree) {
minLength = Math.min(minLength, end - start + 1);
}
}
}
return minLength;
}
const nums1 = [1, 2, 2, 3, 1];
findSmallestLengthBruteForce(nums1); //output: 2
const nums2 = [1, 2, 2, 3, 1, 4, 2];
findSmallestLengthBruteForce(nums2); //output: 6
Solution 2: Hash Map for Frequency and Indices
function findSmallestLengthHashMap(nums) {
const count = {};
const firstIndex = {};
const lastIndex = {};
nums.forEach((num, index) => {
if (!count[num]) count[num] = 0;
count[num]++;
if (firstIndex[num] === undefined) firstIndex[num] = index;
lastIndex[num] = index;
});
const degree = Math.max(...Object.values(count));
let minLength = nums.length;
for (let num in count) {
if (count[num] === degree) {
minLength = Math.min(minLength, lastIndex[num] - firstIndex[num] + 1);
}
}
return minLength;
}
const nums1 = [1, 2, 2, 3, 1];
findSmallestLengthHashMap(nums1); //output: 2
const nums2 = [1, 2, 2, 3, 1, 4, 2];
findSmallestLengthHashMap(nums2); //output: 6
Solution 3: Two-Pass Approach Approach
function findSmallestLengthTwoPass(nums) {
const count = {};
const firstIndex = {};
const lastIndex = {};
nums.forEach((num, index) => {
if (!count[num]) count[num] = 0;
count[num]++;
if (firstIndex[num] === undefined) firstIndex[num] = index;
lastIndex[num] = index;
});
const degree = Math.max(...Object.values(count));
let minLength = nums.length;
Object.keys(count).forEach(num => {
if (count[num] === degree) {
minLength = Math.min(minLength, lastIndex[num] - firstIndex[num] + 1);
}
});
return minLength;
}
const nums1 = [1, 2, 2, 3, 1];
findSmallestLengthTwoPass(nums1); //output: 2
const nums2 = [1, 2, 2, 3, 1, 4, 2];
findSmallestLengthTwoPass(nums2); //output: 6
Solution 4: Sliding Window Approach
function findSmallestLengthSlidingWindow(nums) {
const count = {};
const firstIndex = {};
const lastIndex = {};
nums.forEach((num, index) => {
if (!count[num]) count[num] = 0;
count[num]++;
if (firstIndex[num] === undefined) firstIndex[num] = index;
lastIndex[num] = index;
});
const degree = Math.max(...Object.values(count));
let minLength = nums.length;
for (let start = 0; start < nums.length; start++) {
const currentCount = {};
let end = start;
while (end < nums.length) {
const num = nums[end];
if (!currentCount[num]) currentCount[num] = 0;
currentCount[num]++;
if (currentCount[num] === degree) {
minLength = Math.min(minLength, end - start + 1);
break;
}
end++;
}
}
return minLength;
}
const nums1 = [1, 2, 2, 3, 1];
findSmallestLengthSlidingWindow(nums1); //output: 2
const nums2 = [1, 2, 2, 3, 1, 4, 2];
findSmallestLengthSlidingWindow(nums2); //output: 6
Solution 5: Using Map and Array
function findSmallestLengthMapArray(nums) {
const countMap = new Map();
const firstIndices = new Map();
const lastIndices = new Map();
nums.forEach((num, index) => {
if (!countMap.has(num)) {
countMap.set(num, 0);
firstIndices.set(num, index);
}
countMap.set(num, countMap.get(num) + 1);
lastIndices.set(num, index);
});
const degree = Math.max(...countMap.values());
let minLength = nums.length;
for (let [num, count] of countMap) {
if (count === degree) {
minLength = Math.min(minLength, lastIndices.get(num) - firstIndices.get(num) + 1);
}
}
return minLength;
}
const nums1 = [1, 2, 2, 3, 1];
findSmallestLengthMapArray(nums1); //output: 2
const nums2 = [1, 2, 2, 3, 1, 4, 2];
findSmallestLengthMapArray(nums2); //output: 6
Solution 6: Optimized Frequency Count
function findSmallestLengthOptimizedFrequency(nums) {
const frequency = {};
const firstOccurrence = {};
const lastOccurrence = {};
nums.forEach((num, index) => {
if (!frequency[num]) frequency[num] = 0;
frequency[num]++;
if (firstOccurrence[num] === undefined) firstOccurrence[num] = index;
lastOccurrence[num] = index;
});
const degree = Math.max(...Object.values(frequency));
let minLength = nums.length;
for (const num of Object.keys(frequency)) {
if (frequency[num] === degree) {
minLength = Math.min(minLength, lastOccurrence[num] - firstOccurrence[num] + 1);
}
}
return minLength;
}
const nums1 = [1, 2, 2, 3, 1];
findSmallestLengthOptimizedFrequency(nums1); //output: 2
const nums2 = [1, 2, 2, 3, 1, 4, 2];
findSmallestLengthOptimizedFrequency(nums2); //output: 6
Solution 7: Using Object.entries()
function findSmallestLengthObjectEntries(nums) {
const freq = {};
const firstIndex = {};
const lastIndex = {};
nums.forEach((num, index) => {
if (!freq[num]) freq[num] = 0;
freq[num]++;
if (firstIndex[num] === undefined) firstIndex[num] = index;
lastIndex[num] = index;
});
const degree = Math.max(...Object.values(freq));
let minLength = nums.length;
Object.entries(freq).forEach(([num, count]) => {
if (count === degree) {
minLength = Math.min(minLength, lastIndex[num] - firstIndex[num] + 1);
}
});
return minLength;
}
const nums1 = [1, 2, 2, 3, 1];
findSmallestLengthObjectEntries(nums1); //output: 2
const nums2 = [1, 2, 2, 3, 1, 4, 2];
findSmallestLengthObjectEntries(nums2); //output: 6