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.
1#include <stdio.h>
2#include <stdlib.h>
3
4#define MAX 50000
5
6int findShortestSubarray(int* nums, int numsSize) {
7 int counts[MAX] = {0};
8 int first[MAX];
9 int last[MAX];
10 for (int i = 0; i < MAX; i++) {
11 first[i] = -1;
12 }
13 int degree = 0, minLen = numsSize;
14
15 for (int i = 0; i < numsSize; i++) {
16 int num = nums[i];
17 if (first[num] == -1) {
18 first[num] = i;
19 }
20 last[num] = i;
21 counts[num]++;
22 if (counts[num] > degree) {
23 degree = counts[num];
24 minLen = last[num] - first[num] + 1;
25 } else if (counts[num] == degree) {
26 minLen = (last[num] - first[num] + 1 < minLen) ?
27 (last[num] - first[num] + 1) : minLen;
28 }
29 }
30 return minLen;
31}
32
33int main() {
34 int nums[] = {1, 2, 2, 3, 1};
35 int result = findShortestSubarray(nums, 5);
36 printf("%d\n", result);
37 return 0;
38}This C solution uses arrays to mimic hashmaps due to the constraints. It keeps count of each element's frequency and notes their first and last occurrence. It calculates the degree, then finds the shortest subarray with that 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.
1def
This Python implementation uses defaultdict for frequency and dictionary for storing the first and last occurrence of elements. By doing so, it balances out the computation task into two assemblies.