Minimize the maximum difference between the heights
“Highest climbs have the greatest views.”
We have an array A[] denoting heights of n towers and a positive integer K, we have to modify the height of each tower either by increasing or decreasing them by k only once.
After modifying, height should be a non-negative integer. (i.e., heights can be positive or zero)
Now we have to find out what could be the minimum difference of the height of shortest and longest towers after we have modified height of each tower either by subtracting or by adding k to each tower.
So the approach is pretty simple,
First, we sort the array A
Then we initialize the answer with ans = A[n-1]-A[0], the current minimal max difference between the heights of tower.
Now, in order to maximize the difference between the heights, we will perform the below steps
Since A[0] becomes minimum after sorting, so adding k pushes it towards maximum. Also, we subtract k from A[i] to get any other smaller possible value(minPossible). Similarly, A[n-1] becomes maximum, so subtracting k pushes it towards minimum. Again, we add k to A[i] to get any other maximum possible value(maxPossible).
Next we iterate over the array A[] from 1 to n-1 and implement the above logic and update our ans with min(ans,maxPossible-minPossible) at the end of each iteration.
Here we also check for negative heights before updating ans, i.e. if(minPossible<0) then we do not update ans for that iteration.
Code:
Time Complexity: O(n log n)
Space Complexity: O(n)
Support My Writing: Contribute via UPI or Buy Me a Coffee!
If you enjoyed this post and would like to support my writing, your contributions would be greatly appreciated. You can send your support via UPI at: 6394kp@kotak
