Problem Statement

You are given an array nums containing positive integers. The degree of nums is defined as the maximum frequency of any one of its elements.

Return the minimum length of a contiguous subarray of nums, that has the same degree as nums.

Example

• Example 1:

  • Input: nums = [1, 4, 2, 3, 2]
  • Expected Output: 3
  • Justification: The array's degree is 2 as it appears twice. The shortest subarray with a degree of 2 is [2, 3, 2], which has a length of 3.

• Example 2:

  • Input: nums = [4, 9, 4, 4, 5, 5, 4]
  • Expected Output: 7
  • Justification: Here, the number 4 appears the most (four times). The shortest contiguous segment that includes four 4s is the array itself. So, the answer is 4.

• Example 3:

  • Input: nums = [6, 1, 1, 2, 1, 2, 2]
  • Expected Output: 4
  • Justification: The number 1 appears the most (three times). The shortest subarray capturing all instances of 1 is [1, 1, 2, 1], which has a length of 4.

Solution

To solve this problem, we can use a hash maps data structure. The idea is to first understand the degree of the input array, which involves finding the maximum frequency of any element. Using a hash map, we can track the frequency of each element and simultaneously identify the first and last positions of each element. This allows us to determine the shortest distance for each element that matches the overall degree of the array.

The effectiveness of this approach lies in its ability to simultaneously achieve two objectives: determining the degree of the array and identifying the shortest possible subarray that maintains this degree. By iterating through the array only once to populate our hash maps and then another pass to find the minimum length, we ensure efficiency. This method is preferred because it leverages the power of hash maps for quick look-ups and minimal space overhead, making it a balanced solution in terms of time and space complexity.

Step-by-Step Algorithm

1. Initialize Data Structures: Create three hash maps to keep track of:

   • The frequency of each element (frequency).
   • The index of the first occurrence of each element (firstOccurrence).
   • The index of the last occurrence of each element (lastOccurrence).

2. Populate Maps and Determine Degree: Iterate over the input array (nums) and for each element:

   • Increment its count in the frequency map.
   • Record its index in the firstOccurrence map if it's the first time the element is encountered.
   • Update its index in the lastOccurrence map to the current index (since this might be the last time it appears).
   • Update the degree of the array to the highest frequency encountered so far.

3. Find Shortest Subarray: After populating the maps and determining the degree, iterate through the frequency map to find elements that match the degree. For each such element:

   • Calculate the length of the subarray encompassing all its occurrences, which is the difference between its last and first occurrences plus one.
   • Compare this length with the minimum length found so far and update the minimum length if necessary.

4. Return Result: The minimum length found that satisfies the condition (smallest subarray length that has the same degree as the entire array) is the final result.

Algorithm Walkthrough

Let's consider the input nums = [4, 9, 4, 4, 5, 5, 4].

1. Initialize Data Structures:

   • frequency = {}
   • firstOccurrence = {}
   • lastOccurrence = {}
   • degree = 0, minLength = +∞

2. First Iteration (4):

   • frequency[4] = 1
   • firstOccurrence[4] = 0
   • lastOccurrence[4] = 0
   • degree = 1

3. Second Iteration (9):

   • frequency[9] = 1
   • firstOccurrence[9] = 1
   • lastOccurrence[9] = 1
   • degree = 1 (unchanged)

4. Third Iteration (4 again):

   • frequency[4] = 2 (incremented)
   • firstOccurrence[4] = 0 (unchanged)
   • lastOccurrence[4] = 2 (updated)
   • degree = 2 (updated)

5. Fourth Iteration (4 again):

   • frequency[4] = 3
   • firstOccurrence[4] = 0 (unchanged)
   • lastOccurrence[4] = 3 (updated)
   • degree = 3 (updated)

6. Fifth Iteration (5):

   • frequency[5] = 1
   • firstOccurrence[5] = 4
   • lastOccurrence[5] = 4
   • degree = 3 (unchanged)

7. Sixth Iteration (5 again):

   • frequency[5] = 2
   • firstOccurrence[5] = 4 (unchanged)
   • lastOccurrence[5] = 5 (updated)
   • degree = 3 (unchanged)

8. Seventh Iteration (4 again):

   • frequency[4] = 4
   • firstOccurrence[4] = 0 (unchanged)
   • lastOccurrence[4] = 6 (updated)
   • degree = 4 (updated)

9. Finding Shortest Subarray:

   • Only 4 matches the degree (4 occurrences).
   • The subarray for 4 spans from index 0 to 6 (lastOccurrence[4] - firstOccurrence[4] + 1), resulting in a length of 7.
   • minLength = 7

10. Return Result:

    • The final result is 7, indicating the shortest subarray length that maintains the degree of the entire array is 7 elements long, encompassing all occurrences of the number 4.