Approach Summary
Sort array. Sliding window: window sum ≤ right-end value × window size + k. If total increments needed exceed k, shrink window from left.
How to Recognize This Pattern
- "Max frequency after at most k increments"
- Sort, then check if window can be made uniform within k budget
Complexity Analysis
Time Complexity
O(n log n)
Space Complexity
O(1)
Tags
Array Binary Search Greedy Sliding Window Sorting Prefix Sum