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.
1import java.util.HashMap;
2
3public class DegreeOfArray {
4 public static int findShortestSubarray(int[] nums) {
5 HashMap<Integer, Integer> count = new HashMap<>();
6 HashMap<Integer, Integer> first = new HashMap<>();
7 HashMap<Integer, Integer> last = new HashMap<>();
8 int degree = 0, minLen = nums.length;
9 for (int i = 0; i < nums.length; i++) {
10 int num = nums[i];
11 count.put(num, count.getOrDefault(num, 0) + 1);
12 first.putIfAbsent(num, i);
13 last.put(num, i);
14 degree = Math.max(degree, count.get(num));
15 }
16 for (int key : count.keySet()) {
17 if (count.get(key) == degree) {
18 minLen = Math.min(minLen, last.get(key) - first.get(key) + 1);
19 }
20 }
21 return minLen;
22 }
23
24 public static void main(String[] args) {
25 int[] nums = {1, 2, 2, 3, 1};
26 System.out.println(findShortestSubarray(nums));
27 }
28}In Java, we use HashMaps to track counts, first occurrence, and last occurrence of each number. The method calculates which elements share the array's degree and returns the shortest subarray length matching the 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.
1using System.Collections.Generic;
class DegreeOfArray {
public static int FindShortestSubarray(int[] nums) {
Dictionary<int, int> count = new Dictionary<int, int>();
Dictionary<int, int> first = new Dictionary<int, int>();
Dictionary<int, int> last = new Dictionary<int, int>();
int degree = 0, minLen = nums.Length;
for (int i = 0; i < nums.Length; i++) {
int num = nums[i];
if (!count.ContainsKey(num)) count[num] = 0;
count[num]++;
if (!first.ContainsKey(num)) first[num] = i;
last[num] = i;
degree = Math.Max(degree, count[num]);
}
foreach (int num in count.Keys) {
if (count[num] == degree) {
minLen = Math.Min(minLen, last[num] - first[num] + 1);
}
}
return minLen;
}
static void Main(string[] args) {
int[] nums = { 1, 2, 2, 3, 1 };
Console.WriteLine(FindShortestSubarray(nums));
}
}A double-scan approach designed in C#, manipulating Dictionary-based measurements of counts and positions to manage efficient discovery of subarrays with the right degree.