703022. Smallest subarray with all occurrences of a most frequent element
Medium
Smallest subarray with all occurrences of a most frequent element
Summary
Given an array of integers, find the smallest contiguous subarray that contains all occurrences of the most frequent element. The problem involves arrays and hash data structures.
Detailed Explanation
The approach to solve this problem is to first find the most frequent element in the given array. Then, we will calculate its frequency. After that, we need to find the smallest subarray where all occurrences of this most frequent element are present. We can achieve this by iterating over the array and keeping track of the start index of the current subarray.
Here's a step-by-step breakdown:
- Calculate the frequency of each element in the given array.
- Find the most frequent element (MFE) and its frequency (F).
- Initialize two pointers,
startandend, to the beginning of the array. - Iterate over the array:
- If the current element is not equal to MFE, increment
startuntil we find MFE or reach the end of the array. - If the current element is equal to MFE, check if its frequency (
f) is less than F. If yes, updateendand decrementf.
- If the current element is not equal to MFE, increment
- The subarray
[start, end]will be the smallest contiguous subarray that contains all occurrences of the most frequent element.
Time complexity: O(n), where n is the size of the array. Space complexity: O(min(n, m)), where m is the frequency of the most frequent element.
Optimized Solutions
Java
public int[] smallestSubarray(int[] arr) {
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : arr) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
int maxFreq = 0;
int mfe = -1;
for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
if (entry.getValue() > maxFreq) {
maxFreq = entry.getValue();
mfe = entry.getKey();
}
}
int start = 0;
int end = 0;
int minLen = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == mfe) {
while (i > start && arr[i-1] != mfe) {
start++;
}
end = i;
}
if (end - start + 1 > minLen) {
break;
}
}
return Arrays.copyOfRange(arr, start, end+1);
}