Why does the given solution to this problem works? How can it's correctness be proven?
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 &lt; \cdots &lt; 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 &lt; 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.


Set $M \gets x_n$ (current maximum).
Set $O \gets x_n - x_1$ (smallest span currently known).
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)$.

Return $O$.