Degree of an Array

Question

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

class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer,Integer> numsCountMap = new HashMap<>();
        Map<Integer,Integer> numsLeftIndexMap = new HashMap<>();
        Map<Integer,Integer> numsRightIndexMap = new HashMap<>();
        int smallestLength = nums.length;
        int degree = 0;

        for(int i=0;i<nums.length;i++){

            if(numsLeftIndexMap.get(nums[i]) == null){
                numsLeftIndexMap.put(nums[i],i);
            }
            numsRightIndexMap.put(nums[i],i);
            numsCountMap.put(nums[i],numsCountMap.getOrDefault(nums[i],0)+1);
        }

        degree = Collections.max(numsCountMap.values());

        for(int number: numsCountMap.keySet()){

            if(numsCountMap.get(number) == degree){

               smallestLength= Math.min(smallestLength,
               (numsRightIndexMap.get(number) - numsLeftIndexMap.get(number) + 1));
            }      
        }

        return smallestLength;
        }
    }

Test Cases

  1. An array that contains only one element and with degree as 1. for eg. [0].
  2. An array of more than one element the has degree of 1.for eg. [1,2,3,4,5].
  3. An array with degree > 1 with only one element having highest degree. The element is positioned at the begin and end index of the array. for eg. [1,2,3,4,5,6,1,8,9,1] .
  4. An array with multiple element having highest degree as 2, with one element appearing consecutively.Few of the subarray have same degree. for eg. [1,4,2,6,2,3,3,1,5,12,5].
  5. The entire array is with same element. for eg.[1,1,1,1,1,1,1].
  6. An empty array as input. for eg.[].
  7. An array with max length possible(50,000) and with min(0) and max(49,999) value element as the element having highest degree.
  8. An Array with more than max length possible(eg. 50,001) and element value more than maximum value allowed(eg. 50,000).The output will depend on the requirement (negative testing).

See also