0% completed
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.
- Input: nums =
-
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
.
- Input: nums =
-
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 of4
.
- Input: nums =
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
-
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
).
- The frequency of each element (
-
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.
- Increment its count in the
-
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.
-
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]
.
-
Initialize Data Structures:
frequency = {}
firstOccurrence = {}
lastOccurrence = {}
degree = 0
,minLength = +∞
-
First Iteration (
4
):frequency[4] = 1
firstOccurrence[4] = 0
lastOccurrence[4] = 0
degree = 1
-
Second Iteration (
9
):frequency[9] = 1
firstOccurrence[9] = 1
lastOccurrence[9] = 1
degree = 1
(unchanged)
-
Third Iteration (
4
again):frequency[4] = 2
(incremented)firstOccurrence[4] = 0
(unchanged)lastOccurrence[4] = 2
(updated)degree = 2
(updated)
-
Fourth Iteration (
4
again):frequency[4] = 3
firstOccurrence[4] = 0
(unchanged)lastOccurrence[4] = 3
(updated)degree = 3
(updated)
-
Fifth Iteration (
5
):frequency[5] = 1
firstOccurrence[5] = 4
lastOccurrence[5] = 4
degree = 3
(unchanged)
-
Sixth Iteration (
5
again):frequency[5] = 2
firstOccurrence[5] = 4
(unchanged)lastOccurrence[5] = 5
(updated)degree = 3
(unchanged)
-
Seventh Iteration (
4
again):frequency[4] = 4
firstOccurrence[4] = 0
(unchanged)lastOccurrence[4] = 6
(updated)degree = 4
(updated)
-
Finding Shortest Subarray:
- Only
4
matches the degree (4
occurrences). - The subarray for
4
spans from index0
to6
(lastOccurrence[4] - firstOccurrence[4] + 1
), resulting in a length of7
. minLength = 7
- Only
-
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 number4
.
- The final result is
Code
Complexity Analysis
-
Time Complexity: O(N), where N is the number of elements in the array. This is because the algorithm iterates through the array a constant number of times (exactly twice in most implementations) to populate and then analyze the hash maps.
-
Space Complexity: O(N), where N is the number of elements in the array. In the worst case, if all elements are unique, the space required for the hash maps (
frequency
,firstOccurrence
, andlastOccurrence
) will grow linearly with the size of the input array.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible