Given an array of integers, the cost to change an element is the absolute difference between its initial value and its new value.
For example, if an element is initially 10, it can be changed to 7 or 13 for a cost of 3.
Task. Determine the minimum total cost to make the array sorted along its length — either non-decreasing (ascending) or non-increasing (descending).
Example
n = 6
arr = [0, 1, 2, 5, 6, 5, 7]
- Only
arr[5] = 5violates the ascending order. - If you increase that 5 to 6, the array becomes
arr' = [0, 1, 2, 5, 6, 6, 7] - Cost =
|5 - 6| = 1.
We seek the minimum total edit cost to make an array monotonic (non-decreasing or non-increasing), where editing cost is the L1 distance per element. Use Isotonic Regression (PAV) for ascending; run it on the reversed array for descending and take the minimum. Time O(n), space O(n). Keywords: interview prep, array, greedy/DP, isotonic regression, cheat sheet.
The VOprep team has long accompanied candidates through various major company OAs and VOs, including Apple, Google, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for Tiktok or similar engineering-focused companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.
