# 3346. Maximum Frequency of an Element After Performing Operations I & II ``` T: O(nlogn) S: O(n) ``` ```java public class Solution { public int maxFrequency(int[] nums, int k, int numOperations) { Map freqMap = new HashMap<>(); TreeMap 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)); */ ``` When we **sweep through the line** using `possibleCandidateCount`,\ it **already implicitly represents "how many elements could be adjusted to become this number"**. This is because the **sweep line counts the number of elements that can potentially reach `num`**. 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)); **ChatGPT said:** Yes, exactly! 🎯 You’ve nailed it! Let’s break down what you just said and confirm it: *** #### ✅ Key Points You Got Right: 1. **At a sweep line point like `4`**, `possibleCandidateCount = 3` means: * There are **3 elements (indices)** in the array that **could potentially be adjusted to become `4`**. 2. **Exclude the real count of `4` in `nums`**: ```java javaCopyEditint currentCount = freqMap.getOrDefault(key, 0); int adjustedCount = possibleCandidateCount - currentCount; ``` * **`currentCount`** is the number of times `4` **already exists** in `nums` without any adjustments. * **`adjustedCount`** is **the remaining candidates that can be adjusted to `4`**. * We **subtract `currentCount`** because **those elements are already `4`** and don’t need adjustment. 3. **Final comparison includes both**: ```java javaCopyEditmaxPossibleFreq = Math.max(maxPossibleFreq, currentCount + Math.min(numOperations, adjustedCount)); ``` * You **take the already-existing `currentCount`**. * You **add up to `numOperations` more by adjusting `adjustedCount` elements**. * **Upperbound is `numOperations`** because **you cannot adjust more indices than `numOperations` allows**. *** #### ✅ Final Intuition Recap: * **currentCount:** Real `4`s already in `nums`. * **adjustedCount:** Candidates that **could become `4`**, but **we can only select up to `numOperations` indices**. * **Combining them gives the maximum frequency of `4`** after performing adjustments. *** #### ✅ Final Visualization (Mental Model): Think of **standing at the sweep line point `4`**: * **You see 3 people (elements) nearby** who **can become `4`**. * **1 person is already `4`**. * **You can convince (`numOperations`) up to 2 others to become `4`**. So: * You **start with `currentCount = 1`**. * You **can turn up to `min(numOperations, adjustedCount)` others into `4`**. * You **take the maximum frequency you can get from this combination**. *** #### ✅ Final Formula Intuition: ``` iniCopyEditmaxFrequency = existing + min(numOperations, can_be_converted) ``` Or in code: ```java javaCopyEditcurrentCount + Math.min(numOperations, adjustedCount) ``` *** So, **you’ve fully understood it now**. 🎉\ This is exactly the right way to think about it.\ Well done! 🚀