Leetcode 910: Smallest Range II

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

Notes:

This question is a very tricky one.

Let start with two elements, [A, B], and A <= B. Then what should we do to obtain the minimum of the largest difference?

A can becomes A-K or A+K, and B becomes B-K or B+K.

If we choose the changes with the same direction (either +K or the -K), the largest difference is still B - A.

If we choose different different directions: we have to choose A + K, and B - K, in order to have a smaller largest difference. And the difference is max(A + K, B - K) - min(A + K, B - K).

So the overall minimum largest difference is min(B - A, max(A + K, B - K) - min(A + K, B - K)).

One of the key observations is that: in order to obtain the minimum of the possible largest differences, the smaller elements need to add K, and the larger elements need to minus K.

So now we have [A, B, C, D] as a sorted array.

Similar to the previous example, if we choose the same change, then the largest difference is still D - A.

If we separate the sorted array into two part: the smaller part and the larger part. Let say, [A, B] and [C, D]

then based on the above observation, the smaller part needs to add K, and the larger part needs to minus K, to obtained possible smaller largest difference.

So the smaller part becomes [A + K, B + K], and the larger part becomes [C - K, D - K].

In order to obtain the minimum largest difference, we need to find the largest of the largest elements, and the minimum of the smallest elements.

The former is max(B+K, D-K), and the latter is min(A+K, C-K).

So the global minimum largest difference is min(D - A, max(B+K, D-K) - min(A+K, C-K)).

Actually, we can split the array into two parts at any position from (1, to n-1), if there are n elements.

So the general formula is:

1): sort the array;

2): the minimum largest difference is

min(largestV - smallestV, max(V[i-1] + K, largestV - K) - min(V[i] - K, smallestV + K)), for i from 1 to n.


Thus, this question can be solved greedily, and TC is O(NlogN) and SC is O(1).

See the code below:

class Solution {
public:
    int smallestRangeII(vector<int>& A, int K) {
        sort(A.begin(), A.end());
        int res = A.back() - A.front();
        for(int i=1; i<A.size(); ++i) {
            int mn = min(A.front() + K, A[i] - K), mx = max(A[i-1] + K, A.back() - K);
            res = min(res, mx - mn);
        }
        return res;
    }
};