703416. Maximum value K
Maximum value K
Slug: maximum-value-k2745 Difficulty: Easy Id: 703416 Topic Tags: Arrays, Data Structures Company Tags: None
Summary
Given an array of integers, find the maximum value that occurs at least K times in the array. The input array is not necessarily sorted.
This problem involves arrays and data structures, requiring a solution that can efficiently handle repeated values and their counts.
Detailed Explanation
The approach to solve this problem involves using a frequency count of the elements in the array. We iterate through the array once to calculate the frequency of each element. Then, we iterate through the frequency map to find the maximum value that occurs at least K times.
Here's the step-by-step breakdown:
- Create an empty hash map (
freqMap) to store the frequency of each element in the array. - Iterate through the array and for each element:
- Check if it's already present in
freqMap. If not, add it with a count of 1. If it is, increment its count by 1.
- Check if it's already present in
- Initialize
maxValueto -∞ (or any value smaller than all possible values in the array). - Iterate through
freqMapand for each element:- Check if its frequency is at least
K. If not, skip this iteration. - Update
maxValueif the current element's value is greater thanmaxValue.
- Check if its frequency is at least
- Return
maxValue.
Time complexity: O(n), where n is the size of the input array.
Space complexity: O(min(n, m)), where m is the maximum possible frequency of an element in the array.
Optimized Solutions
Java
public int maxFrequency(int[] arr, int K) {
Map<Integer, Integer> freqMap = new HashMap<>();
int maxValue = -Integer.MAX_VALUE;
for (int num : arr) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
if (entry.getValue() >= K) {
maxValue = Math.max(maxValue, entry.getKey());
}
}
return maxValue;
}