https://leetcode.com/problems/smallest-range-ii

In this problem we need to add K to some numbers and subtract K from some numbers, such that final gap between minimum and maximum number is minimal. Notice, that it is equivalent to just subtracting 2*K from some subset of numbers we have. Imagine, that we choose indexes i_1 < ... < i_l for numbers we want to subtract 2K from. How we can find now gap between minimum and maximum elements?

  1. We choose i_1 < ... < i_l indexes for numbers we want to subtract 2*K, let us define j_1 < ... < j_m indexes for numbers we do not touch.
  2. Then we can look at it as following: we have segment A[i_1] - 2*K to A[i_l] - 2*K and we have segment A[j_1] to A[j_m] and we need to find maximum distance between ends of these segments. Notice now, that if segments [i_1, i_l] and [j_1, j_m] have intersections, than we can decrease size of one of them, so final gap between maximum and minimum values can only decrease.
  3. It means it fact, that indexes we choose follow the pattern: 0, ..., i for first set and i+1, ..., n-1 for the second set: we do not touch elements in first group and subtract 2*K from elements from second group. Notice also, that there is case, when one of the groups is empty, in this case, gap will be A[-1] - A[0].

Complexity: it is O(n log n) to sort data and O(n) to traverse it, leading to O(n log n) final complexity. Additional space complexity is O(log n) if we sort in place (note, that sort in place will not be O(1), but O(log n)).

class Solution:
    def smallestRangeII(self, A, K):
        A.sort()
        n, ans = len(A), float("inf")

        for i in range(n-1):
            cands = [A[0], A[i], A[i+1] - 2*K, A[-1] - 2*K]
            ans = min(ans, max(cands) - min(cands))
            
        return min(ans, A[-1] - A[0])

If you like the solution, you can upvote it on leetcode discussion section: Problem 0910