{x}
blog image

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.length will be between 1 and 50,000.
  • nums[i] will be an integer between 0 and 49,999.

Solution Explanation for LeetCode 697: Degree of an Array

This problem asks to find the length of the shortest contiguous subarray that contains the maximum frequency element(s) of the input array. We'll explore efficient solutions using hash maps to track element counts, first and last occurrences.

Approach 1: Using Hash Maps for Efficient Tracking

This approach leverages three hash maps:

  1. cnt: Stores the frequency of each element.
  2. left: Stores the index of the first occurrence of each element.
  3. right: Stores the index of the last occurrence of each element.

The algorithm proceeds as follows:

  1. Count Frequencies: Iterate through nums to populate cnt. Simultaneously, update left and right to track first and last occurrences.
  2. Find Maximum Degree: Determine the maximum frequency (degree) from cnt.
  3. Find Shortest Subarray: Iterate through nums. For each element with frequency equal to degree, calculate the subarray length (right[v] - left[v] + 1). Track the minimum length encountered.

Time Complexity: O(N), where N is the length of nums. We iterate through the array three times (once for counting, once for finding the maximum degree, and once for finding the shortest subarray). Hash map operations (insertion, lookup) are O(1) on average.

Space Complexity: O(N) in the worst case, as the hash maps could store all unique elements from nums.

Code (Python, Java, C++, Go): (Provided in the original prompt) The code in each language efficiently implements this approach. Note the use of Counter in Python for concise frequency counting.

Approach 2: More concise Go Implementation (Alternative)

This approach uses a slightly different structure but achieves the same result in a more concise Go implementation. It first identifies the elements with the maximum degree then finds the shortest subarray length for each element individually.

Time Complexity: O(N) - Similar to Approach 1, due to the iterations involved.

Space Complexity: O(N) - The numsMap could store all unique elements.

Code (Go): (Provided in the original prompt). The functions getMaxDegreeElem, findSubArray, getStartIdx, and getEndIdx break down the process into smaller, more manageable parts. min and max are helper functions to find the minimum and maximum values.

Choosing the Best Approach:

Both approaches have the same time and space complexity. Approach 1 might be considered slightly more readable due to its straightforward structure. Approach 2 (Go) demonstrates a potentially more concise approach suitable for Go developers familiar with its functional features. The choice depends on personal preference and coding style.