Arena Rating Ramp
Farthest end per start for array intervals made nondecreasing by budgeted raises
An online game's replay editor stores a combat rating for each round in chronological order. To create a progression clip, the editor selects a contiguous interval of rounds and raises some of its ratings until the selected ratings are nondecreasing.
Raising one round's rating by one costs one upgrade credit. Ratings may only be raised, never lowered, and there is no upper limit on the raised values. Each candidate clip gets its own budget of budget credits; upgrades made for one clip do not affect any other clip.
Given the integer array ratings and the integer budget, return an array ends of the same length. For every starting index i, ends[i] must be the largest inclusive ending index j such that the interval ratings[i..j] can be made nondecreasing using at most budget credits.
Indices are zero-based. A single-round interval always qualifies. If ratings is empty, return an empty array.
Examples
Example 1
Input: ratings = [4,1,2,5], budget = 3 Output: [1,3,3,3]
For the clip starting at index 0, raising the second rating from 1 to 4 costs three credits. Including the third round would require another two credits, exceeding the budget. Starting at index 1, the remaining ratings are already nondecreasing.
Example 2
Input: ratings = [2,2,1,3,0], budget = 0 Output: [1,1,3,3,4]
With no credits, each clip must already be nondecreasing. Equal neighboring ratings are permitted, but a clip cannot cross a decrease.
Example 3
Input: ratings = [-2,-4,-3,0], budget = 3 Output: [3,3,3,3]
Negative ratings follow the same rules. Starting at index 0, raising the next two ratings to -2 costs three credits in total, and the final rating needs no change.
Constraints
- 0 <= ratings.length <= 16000
- -10^9 <= ratings[i] <= 10^9
- 0 <= budget <= 10^14
- ratings and budget contain integers.
An O(n) time, O(n) space solution is expected. JavaScript Number arithmetic is exact for all integer quantities needed under these constraints.
Hints
Show hint 1Hint 1
For a fixed interval, the cheapest raised rating at each position is the maximum original rating seen so far within that interval.
Show hint 2Hint 2
Process starting indices from right to left. Track the plateaus of prefix maxima with a monotonic deque, and move the ending index left whenever the upgrade cost exceeds the budget.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also return the minimum upgrade cost of each chosen interval?
- How would the algorithm change if raising rating i by one cost a positive weight weights[i]?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem