# 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<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`**:

    ```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! 🚀
