Weather Trace Retuning
Endpoints of the longest subarray equalizable within an absolute-change budget
A weather station stores an ordered trace of integer readings. A technician wants to select one nonempty contiguous interval and retune every reading in that interval to the same integer value.
Changing a reading from x to t costs |x - t| adjustment units. The technician may choose any integer target t, including a value that does not appear in the trace. The total cost is the sum of the adjustment costs for all readings in the selected interval. Readings cannot be deleted or reordered.
Given the array readings and a nonnegative adjustment budget, return the inclusive, zero-based endpoints [start, end] of the longest interval that can be retuned within the budget.
If several intervals have the same maximum length, return the one with the smallest start. If readings is empty, return [].
Examples
Example 1
Input: readings = [3,4,4,12], budget = 1 Output: [0,2]
In the first three readings, choosing target 4 requires one adjustment unit for the reading 3 and none for the other two. Any interval that also includes the isolated reading 12 is more expensive.
Example 2
Input: readings = [7,7,-2,-2,5], budget = 0 Output: [0,1]
With no adjustment units available, only intervals whose readings are already equal are eligible. The two longest constant runs have the same length, so the earlier run is selected.
Example 3
Input: readings = [-5,1,-2,4], budget = 12 Output: [0,3]
Negative readings are allowed. For the entire trace, any integer target between the two middle sorted readings has the same minimum cost, which fits the available budget. The target itself is not part of the returned answer.
Constraints
- 0 <= readings.length <= 10000
- -1000000000 <= readings[i] <= 1000000000
- 0 <= budget <= 10000000000000
- All readings and the budget are integers.
The intended solution runs in O(n log n) time and O(n) auxiliary space. Lazy-deleted heap entries may remain stored until they reach a heap root. All required arithmetic is within JavaScript's exact integer range.
Hints
Show hint 1Hint 1
For a fixed interval, a median minimizes the sum of absolute distances. Adding a reading cannot decrease this minimum cost, which permits a shrinking sliding window.
Show hint 2Hint 2
Maintain the lower and upper halves of the window in two heaps, together with each half's sum. Use lazy deletion by index when the left endpoint advances.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would the algorithm simplify if the target reading were supplied instead of chosen freely?
- If each reading had a positive adjustment weight, how would the optimal target and the maintained data structure change?
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