Exchange Quote Staircase
Lexicographically first nondecreasing array minimizing weighted absolute error
A stock exchange publishes a sequence of auction checkpoints. Each checkpoint has a proposed quote offset, measured in integer ticks relative to a reference price. Negative offsets are allowed.
Before publication, the exchange must replace these offsets with a nondecreasing sequence of integer offsets. Checkpoint i has an importance weight weights[i]; replacing its proposed offset prices[i] with adjusted[i] incurs a correction cost of
weights[i] * abs(adjusted[i] - prices[i]).
Return a nondecreasing integer array adjusted of the same length that minimizes the total correction cost.
If multiple arrays attain the minimum cost, return the lexicographically smallest one: at the first index where two arrays differ, the array with the smaller value comes first.
For an empty input sequence, return an empty array.
Examples
Example 1
Input: prices = [7,1,9], weights = [1,1,1] Output: [1,1,9]
The first two proposed offsets are out of order. Because their weights are equal, setting both to any integer between their proposals has the same correction cost. The lexicographic rule chooses the smallest such value; the final checkpoint can remain unchanged.
Example 2
Input: prices = [8,2,10], weights = [5,1,1] Output: [8,8,10]
The first checkpoint is much more important than the second. It is cheaper to raise the second offset to match the first than to lower the first. The last offset already fits after this correction.
Example 3
Input: prices = [-4,-4,0,6], weights = [2,7,3,1] Output: [-4,-4,0,6]
The proposed offsets are already nondecreasing, including an equal adjacent pair, so no corrections are needed.
Constraints
- 0 <= prices.length <= 4000
- weights.length == prices.length
- -100000 <= prices[i] <= 100000
- 1 <= weights[i] <= 100000
- All input values and returned offsets are integers.
The intended solution takes O(n log n) time and O(n) space. Heap entries represent weighted price levels rather than individual units of weight, so large weights must not be expanded. All costs permitted by the constraints fit within JavaScript's exact integer range.
Hints
Show hint 1Hint 1
A constant block minimizes weighted absolute error at a weighted median. When an interval of medians is optimal, its lower endpoint is relevant to lexicographic tie-breaking.
Show hint 2Hint 2
Process checkpoints from left to right with a max-heap of price levels carrying weight. Insert twice the new weight, cancel one new weight from the largest levels, and record the remaining maximum. A backward pass can enforce compatibility between these recorded bounds.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also compute the minimum total correction cost without changing the asymptotic complexity?
- How can you adapt the solution if successive published offsets must increase by at least a fixed positive integer gap?
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