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

Question

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
            big = add;
    }

    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?

Answer 1

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$.