697. Degree of an Array #

Problem #

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.

Problem Summary #

Given a non-empty integer array containing only non-negative numbers, nums, the degree of the array is defined as the maximum frequency of any element in the array. Your task is to find the shortest contiguous subarray that has the same degree as nums and return its length.

Note:

• nums.length is in the range from 1 to 50,000.
• nums[i] is an integer in the range from 0 to 49,999.

Solution Approach #

• Find the shortest contiguous subarray with the same degree as the given array and output its length. The degree of an array is defined as the maximum frequency of any element.
• Easy problem. First count the frequency of each element, and dynamically maintain the maximum frequency as well as the starting and ending positions of the subarray. The “shortest contiguous subarray” here is a bit “misleading”. This shortest subarray is actually very simple to handle. Just scan from front to back once, and record the first occurrence position and last occurrence position of each element; that is the shortest contiguous subarray for that element. Then, in the frequency dictionary, find all solutions with the same frequency as the maximum frequency. There may be multiple subarrays that satisfy the requirement, so take the shortest one and output it.

Code #

package leetcode

func findShortestSubArray(nums []int) int {
	frequency, maxFreq, smallest := map[int][]int{}, 0, len(nums)
	for i, num := range nums {
		if _, found := frequency[num]; !found {
			frequency[num] = []int{1, i, i}
		} else {
			frequency[num][0]++
			frequency[num][2] = i
		}
		if maxFreq < frequency[num][0] {
			maxFreq = frequency[num][0]
		}
	}
	for _, indices := range frequency {
		if indices[0] == maxFreq {
			if smallest > indices[2]-indices[1]+1 {
				smallest = indices[2] - indices[1] + 1
			}
		}
	}
	return smallest
}