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));
 */

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:

   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:

   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 4s 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:

javaCopyEditcurrentCount + Math.min(numOperations, adjustedCount)

---

So, you’ve fully understood it now. 🎉 This is exactly the right way to think about it. Well done! 🚀