Hi, I came across this problem where you are given an array a, your task is to convert it into a non-increasing form such that we can either increment or decrement the array value by 1 in minimum changes possible.

One approach that I could think of using dp where dp[i][j] stood for minimum number of changes for first i elements if we use the largest j heights in the original array.

This approach has time complexity of O(N^2) and space complexity of O(N). But there seems to be better approach as mentioned in this blog https://www.geeksforgeeks.org/minimum-incrementdecrement-to-make-array-non-increasing/. But I was neither able to understand the approach described nor the code given.

But I checked the correctness of the code in the blog against my dp code. Both of them were producing same results. So if anyone could let me know how the O(N*log(N)) solution works that would be great.