# Why does the given solution to this problem works? How can it's correctness be proven?

This is a question asked in Adobe interview:

Given heights of n towers and a value k. We need to either increase or decrease height of every tower by k (only once) where k > 0. The task is to minimize the difference between the heights of the longest and the shortest tower after modifications, and output this difference.

Link of problem and it's solution: solution and problem

Solution posted at the website(click on the link above):

// C++ program to find the minimum possible
// difference between maximum and minimum
// elements when we have to add/subtract
// every number by k
#include <bits/stdc++.h>
using namespace std;

// Modifies the array by subtracting/adding
// k to every element such that the difference
// between maximum and minimum is minimized
int getMinDiff(int arr[], int n, int k)
{
if (n == 1)
return 0;

// Sort all elements
sort(arr, arr+n);

// Initialize result
int ans = arr[n-1] - arr[0];

// Handle corner elements
int small = arr[0] + k;
int big = arr[n-1] - k;
if (small > big)
swap(small, big);

// Traverse middle elements
for (int i = 1; i < n-1; i ++)
{
int subtract = arr[i] - k;
int add = arr[i] + k;

// If both subtraction and addition
// do not change diff
if (subtract >= small || add <= big)
continue;

// Either subtraction causes a smaller
// number or addition causes a greater
// number. Update small or big using
// greedy approach (If big - subtract
// causes smaller diff, update small
// Else update big)
if (big - subtract <= add - small)
small = subtract;
else
}

return  min(ans, big - small);
}

// Driver function to test the above function
int main()
{
int arr[] = {4, 6};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 10;
cout << "\nMaximum difference is "
<< getMinDiff(arr, n, k);
return 0;
}


After trying for around an hour. This is the solution I came up with:

1. Sort the array in non decreasing order.
2. Initialise two pointers, one at the starting(0th index) and other at the end(n-1 th index) of the array. If the difference between the values at the two pointers is greater than or equal to twice of k, then increment the value at the left pointer by k and decrement the value at the left pointer by k. Get the difference between the new values and update the variable that stores the minimum answer.
3. Increment left pointer and decrement right pointer.
4. Repeat steps 2 and 3 until left and right pointers converge to the same address.

But the algorithm I wrote only passed sample test cases. When I looked at the editorial, I could not understand why the solution works the way it does. Can anyone break it down step by step.

Also I read in comments it can be solved in O(N). Would be thankful if someone can put insight if that's possible and how. Also where can I practice similar questions?

• I don't think this question is a good fit for the site. You've presented us with your solution to a problem and you're essentially asking us to grade that for you. That's not something that's ever going to be useful to anyone else, unless somebody else happens to produce exactly the same answer. You also ask us how some other solution works but you don't tell us what that solution is; you just give us a link to some other site. Questions need to be self-contained. But even then, "Please explain this thing to me" isn't a very good question because you don't say what it is you don't... – David Richerby Feb 10 '18 at 17:08
• ... understand about the solution you've already seen. It's hard to guess what level to explain it at. – David Richerby Feb 10 '18 at 17:08
• David Richerby: If you scroll down to the website I have given link of, you will find the correct solution there. I was asking how and why that solution works. Moreover, I don't necessarily need someone to explain the solution posted at the website, if someone can explain his/her own working solution, it would still be ok. I Googled before posting the question here but nowhere found an explanation on how to solve the problem. If it is not a correct place to ask algorithm questions, can you please tell me where else should I go? Anyway for convenience I have added the working solution here. – Sourabh Khandelwal Feb 10 '18 at 17:17
• you will find the correct solution I don't. I find one solution - looking correct, but outrageously complicated and inefficient. – greybeard Apr 12 '18 at 9:42

There's a simple $O(n\log n)$ solution. It also sounds plausible that there is a linear time solution, but it seems to require a bit of case analysis.

First of all, instead of either decreasing by $k$ or increasing by $k$, we can first decrease all values by $k$, and then either not change the value or increase it by $\Delta := 2k$.

Suppose now that the sorted list is $x_1 < \cdots < x_n$. We first show that without loss of generality, an optimal solution increases a prefix of the sorted list. Indeed, consider a solution $y$ which increases $x_{i+1}$ but not $x_i$. Let us consider an alternate solution $z$ which doesn't increase $x_{i+1}$. Denote by $s(y),s(z)$ the span of the solution, which is the objective we're trying to minimize. If $s(y) \neq s(z)$ then $s(z)$ involves $z_{i+1}$, and so $z_{i+1}$ is an extreme point of $z$. Since $z_i < z_{i+1}$, necessarily $z_{i+1}$ is a maximum. Let $z_j$ be the other extreme point of $z$. Since $y_j = z_j$, we see that $s(y) \geq y_{i+1} - y_j = z_{i+1} + \Delta - z_j = s(z) + \Delta$, and so $z$ improves over $y$. We conclude that any optimal solution which increases $x_{i+1}$ must also increase $x_i$, and so also $x_{i-1},\ldots,x_1$, and generally increases a prefix of $x$.

The $O(n\log n)$ algorithm first sorts the list, and then considers all possible increases of prefixes. The idea is to consider what happens when not changing the list, when increasing $x_1$, then $x_1,x_2$, then $x_1,x_2,x_3$, and so on. At each point of this process, we need to know the span of the solution under consideration. When increasing $x_1,\ldots,x_i$, the minimum is always $x_{i+1}$ (there is no need to consider the case $i=n$). We can determine the maximum in an online fashion: if the maximum is $M$ before increasing $x_i$, then after increasing $x_i$ it is $\max(M,x_i+\Delta)$.

Here is the resulting algorithm, which assumes that we have already sorted the list.

1. Set $M \gets x_n$ (current maximum).
2. Set $O \gets x_n - x_1$ (smallest span currently known).
3. For $i=1,\ldots,n-1$:
• Set $M \gets \max(x_i+\Delta,M)$.
• Set $S \gets M-x_{i+1}$ (current span).
• Set $O \gets \min(O,S)$.
4. Return $O$.