703670. Difference between highest and lowest occurrence
Difference between highest and lowest occurrence
Summary
Given an array of integers, find the difference between the highest and lowest occurrence of each integer in the array. The problem is about finding the range of occurrences for each element in the array.
Detailed Explanation
The problem can be solved by using a hash map to store the frequency of each element in the array. Then, we iterate through the hash map to find the maximum and minimum frequencies for each element, which gives us the difference between the highest and lowest occurrence.
Here's a step-by-step breakdown:
- Create an empty hash map to store the frequency of each element.
- Iterate through the array and increment the count for each element in the hash map.
- Initialize two variables
max_frequencyandmin_frequencyto keep track of the maximum and minimum frequencies, respectively. - Iterate through the hash map again and update
max_frequencyandmin_frequencyfor each element. - Calculate the difference between
max_frequencyandmin_frequencyto find the range of occurrences for each element.
Time complexity: O(n), where n is the size of the array, as we are iterating through the array once to build the hash map and again to update the maximum and minimum frequencies.
Space complexity: O(m), where m is the number of unique elements in the array, as we need to store the frequency of each element in the hash map.
Optimized Solutions
Java
import java.util.HashMap;
import java.util.Map;
public class HighestAndLowestOccurrence {
public static int[] findDifference(int[] arr) {
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : arr) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
int[] result = new int[arr.length];
int maxFrequency = 0;
int minFrequency = Integer.MAX_VALUE;
for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
if (entry.getValue() > maxFrequency) {
maxFrequency = entry.getValue();
}
if (entry.getValue() < minFrequency) {
minFrequency = entry.getValue();
}
}
for (int i = 0; i < arr.length; i++) {
result[i] = Math.abs(maxFrequency - minFrequency);
}
return result;
}
}