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.

Solution(javascript)

/**
 * @param {number[]} nums
 * @return {number}
 */
const findShortestSubArray = function (nums) {
  let degree = 0
  let length = Infinity
  nums.reduce((acc, num, index) => {
    if (acc[num] !== undefined) {
      acc[num].degree += 1
      acc[num].range[1] = index
    } else {
      acc[num] = {
        degree: 0,
        range: [index, index],
      }
    }
    if (acc[num].degree > degree) {
      degree = acc[num].degree
      length = acc[num].range[1] - acc[num].range[0] + 1
    } else if (acc[num].degree === degree) {
      length = Math.min(
        length,
        acc[num].range[1] - acc[num].range[0] + 1,
      )
    }
    return acc
  }, {})
  return length
}