Sponsored
Sponsored
This approach involves creating a HashMap for tracking the frequency of each element, and two other HashMaps to keep track of the first and last indices of each element. The goal is to determine the degree of the array, then find the shortest subarray that has this same degree.
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(n), due to the usage of the arrays to track counts and positions.
1def findShortestSubarray(nums):
2 from collections import defaultdict
3 count = defaultdict(int)
4 first, last = {}, {}
5 degree, minLen = 0, len(nums)
6
7 for i, num in enumerate(nums):
8 count[num] += 1
9 if num not in first:
10 first[num] = i
11 last[num] = i
12 degree = max(degree, count[num])
13
14 for num in count:
15 if count[num] == degree:
16 minLen = min(minLen, last[num] - first[num] + 1)
17
18 return minLen
19
20if __name__ == "__main__":
21 nums = [1, 2, 2, 3, 1]
22 print(findShortestSubarray(nums))This Python solution uses collections' defaultdict to manage count tracking and maintains dictionaries for the first and last positions. It efficiently determines the shortest subarray with the array's degree.
This approach first calculates the degree of the array in a single pass, then performs a second traversal to identify the smallest contiguous subarray with the same degree. The second traversal uses the frequency and position data collected during the first pass.
Time Complexity: O(n), needing two passes over n elements.
Space Complexity: O(n), primarily due to the need to store index locations.
1#include <vector>
#include <unordered_map>
using namespace std;
int findShortestSubarray(vector<int>& nums) {
unordered_map<int, int> count, first, last;
int degree = 0, minLen = nums.size();
for (int i = 0; i < nums.size(); i++) {
int num = nums[i];
count[num]++;
if (first.find(num) == first.end()) {
first[num] = i;
}
last[num] = i;
degree = max(degree, count[num]);
}
for (const auto& entry : count) {
if (entry.second == degree) {
int num = entry.first;
minLen = min(minLen, last[num] - first[num] + 1);
}
}
return minLen;
}
int main() {
vector<int> nums = {1, 2, 2, 3, 1};
cout << findShortestSubarray(nums) << endl;
return 0;
}In C++, the approach leverages unordered_maps to handle counts and indices. These mappings allow an efficient second pass to quickly determine the shortest subarray with the necessary degree.