3346. Maximum Frequency of an Element After Performing Operations I & II
T: O(nlogn)
S: O(n)public class Solution {
public int maxFrequency(int[] nums, int k, int numOperations) {
Map<Integer, Integer> freqMap = new HashMap<>();
TreeMap<Integer, Integer> sweepLineMap = new TreeMap<>();
for (int num : nums) {
freqMap.put(num, freqMap.getOrDefault(num, 0)+1);
sweepLineMap.putIfAbsent(num, 0); // need to include the point in original nums[], not just start, end
sweepLineMap.put(num - k, sweepLineMap.getOrDefault(num - k, 0)+1); // start
sweepLineMap.put(num + k + 1, sweepLineMap.getOrDefault(num + k + 1, 0)-1); // end
}
int maxPossibleFreq = 0;
int possibleCandidateCount = 0;
for (int key : sweepLineMap.keySet()) {
// how many elements could be adjusted to become this number
possibleCandidateCount += sweepLineMap.get(key); // caculate the sweep count
int currentCount = freqMap.getOrDefault(key, 0);
int adjustedCount = possibleCandidateCount - currentCount;
maxPossibleFreq = Math.max(maxPossibleFreq, currentCount + Math.min(numOperations, adjustedCount));
}
return maxPossibleFreq;
}
}
/**
so case is
freq map -> get current count
because this question is talk about adding different number to a nums[i]
so we can use sweepline idea.. to define start and end for a range of nums[i]
ex: [1,4,5]
-> for 1
1 - k. (start)
1 + k + 1. (end)
calculate the freq count for them
1-1 = 0
1+1+1 = 3
4-1 = 3
4+1+1 = 6
5 - 1 = 4
5+1+1 = 7
sweeplineMap
+ -
0 ---- 3
+ -
3 ---- 6
+ -
4------7
1 1 2 1 0
freqMap
1: 1
4: 1
5: 1
for sweepline key
adjusted_count = possible (include current real count) - current
numOperations = 2
for (0. 3 4. 6 7)
possibleCandidateCount += sweepLineMap.get(key); // caculate the sweep count
// when 0 -> possibleCandidateCount = 1
// currentCount = 0
// adjusted_count = 1 - 0
// maxFrequency = Math.max(maxFrequency, 0 + Math.min(2, 1) = 1
...
when 4 -> possibleCandidateCount = 2
// currentCount = 1
// adjusted_count = 2 - 1 = 1
// maxFrequency = Math.max(maxFrequency, 1 + Math.min(2, 1) = 2
... result is 2
and build possible Freq map (include current real count, because we add the range number on it)
adjusted_count = possible (include current real count) - current
-> maxFrequency = Math.max(maxFrequency, currentCount(freq map) + Math.min(numOperations, adjusted_count)) (possible count map (may become that num, but limit to numOperations only can change numOperations times));
T: O(nlogn)
S: O(n)
Conclusion:
oh, I think I got it, the sweepline point, like 4, and it has count 3,
means there are 3 elements could be adjusted to become 4
and so that's why we need to exclude the real count in 4
int currentCount = freqMap.getOrDefault(key, 0);
int adjustedCount = possibleCandidateCount - currentCount;
and in the end still count the currentCount in last comparing
and adjustedCount's upperbound is numOperations (how many different elements can be changed)
maxPossibleFreq = Math.max(maxPossibleFreq, currentCount + Math.min(numOperations, adjustedCount));
*/
✅ Key Points You Got Right:
✅ Final Intuition Recap:
✅ Final Visualization (Mental Model):
✅ Final Formula Intuition:
Last updated