This is my first blog post.
It would be great if someone could explain their approach.
You are given a list of integers nums and an integer k. Consider an operation where you increment any one element once. Given that you can perform this at most k times, return the resulting value of the most frequently occurring number. If there's more than one solution, pick the smallest possible number.
Constraints : n ≤ 100,000 where n is the length of nums.
TestCase : nums = [1, 1, 1, 2, 2, 2, 4, 4, 4, 4] k = 3
Output : 2
Explanation :
After we increment the 1s, we get [2, 2, 2, 2, 2, 2, 4, 4, 4, 4]
**Link : https://binarysearch.io/problems/Most-Occurring-Number-After-K-Increments**
shows that the response is an element in the array.
sort the array and find out how to extend a specific element (to right? to left?).
I'm sorry Can you explain it in little brief.
first, the answer has to be an element greater than or equal to the minimum.
suppose the response is not an element in the array, then there is a maximum element in my original array that is less than that element.
then we can remove (final number of repetitions) x (answer — maximum element found) and reduce the number of operations and at the same time find a smaller result (this is a contradiction, the answer is not smaller).
now that we know the answer is an element of the array, we can fix this and not think of larger elements.
Once the answer is fixed, we can greedily improve the answer, choosing the elements that are larger but at the same time smaller than my answer and gradually increasing them.
this sounds like an $$$O(n^2)$$$, but it is not the case, we can make an improvement if we do a binary search, we set a position in the ordered array (we can use sort function with a complexity of $$$O(n \log n)$$$) and fix as far as I can extend said element to the left (make all a fixed number of elements equal to the answer), we can do this by carrying accumulated and checking that $$$({answer} ~x~ {len}) - ({sum}_i - {sum}_{i - len}) \le k$$$.
final complexity $$$O(n \log n)$$$, as a note, if you had the ordered array in the input, there would be a linear solution with two pointers.
P.S: There are several more approaches, this would not be the only one, it is not necessary to use binary search but at the same time I consider that it is very useful and simplifies problems a lot.
Solution
Harder variant: https://binarysearch.io/problems/Longest-Equivalent-Sublist-After-K-Increments
history repeats itself