LeetCode 910 - Smallest Range II

Related: LeetCode 908 - Smallest Range I
LeetCode 910 - Smallest Range II
https://leetcode.com/problems/smallest-range-ii/

Given an array A of integers, for each integer A[i] we need to choose either x = -K or x = K, and add x to A[i] (only once).

After this process, we have some array B.

Return the smallest possible difference between the maximum value of B and the minimum value of B.

Example 1:

Input: A = [1], K = 0
Output: 0
Explanation: B = [1]

Example 2:

Input: A = [0,10], K = 2
Output: 6
Explanation: B = [2,8]

Example 3:

Input: A = [1,3,6], K = 3
Output: 3
Explanation: B = [4,6,3]

http://www.noteanddata.com/leetcode-910-Smallest-Range-II-solution-note.html
https://www.acwing.com/solution/LeetCode/content/718/
我们肯定期望在较小的数字上增加 K，在较大的数组上减少 K，所以首先将数组 A 从小到大排序。
初始化答案为 A[n - 1] - A[0]；然后依次枚举每个位置 i，计算此时的最小值 min(A[0] + K, A[i + 1] - K) 和最大值 max(A[i] + K, A[n - 1] - K)，然后更新答案。
https://blog.csdn.net/XX_123_1_RJ/article/details/82850678
这个题目还是比较有意思的，看了评论才搞明白，排序，然后线性扫描就可以得出结果。
（1）先有这样一个知识，假设a < b，那么[a + k， b - k]，一定是[a - k， b + k]的一个子集，后面的计算，就可以在[a + k， b - k] 区间里面寻找了。
（2）首先对整个数组从小到大排序，方便后面计算，并且确定一个上界 res = A[-1] - A[0] （其中这个上界，包含了两个数同时加上或者减轻 K的情况）。
（3）排序后，来看一种情况，假设数组A在i处被分割为两部分[ A[1], A[2], A[3]... A[i] ]、[ A[i+1], A[i+2], A[i+3]... A[n-1] ] 现在可以把这两部分，看成两个值，然后考虑（1）中的情况，遍历选出最优的结果。如果说存在贪心思想，感觉，在选取i的情况下，可以说是贪心的选取得
https://www.cnblogs.com/pk28/p/9696276.html
贪心，先排序，然后结果肯定是选个位置pos,pos之前的元素都+k之后的元素都-k,那么我们就枚举这个位置，然后进行判断，首先pos这个位置一定是把数组分成两个递增的序列，那么我们枚举4个值就可以了

As in Smallest Range I, smaller A[i] will choose to increase their value ("go up"), and bigger A[i] will decrease their value ("go down").

Algorithm

We can formalize the above concept: if A[i] < A[j], we don't need to consider when A[i] goes down while A[j] goes up. This is because the interval (A[i] + K, A[j] - K) is a subset of (A[i] - K, A[j] + K) (here, (a, b) for a > b denotes (b, a) instead.)

That means that it is never worse to choose (up, down) instead of (down, up). We can prove this claim that one interval is a subset of another, by showing both A[i] + K and A[j] - K are between A[i] - Kand A[j] + K.

For sorted A, say A[i] is the largest i that goes up. Then A[0] + K, A[i] + K, A[i+1] - K, A[A.length - 1] - K are the only relevant values for calculating the answer: every other value is between one of these extremal values.

    public int smallestRangeII(int[] A, int K) {

        int N = A.length;

        Arrays.sort(A);

        int ans = A[N-1] - A[0];

        for (int i = 0; i < A.length - 1; ++i) {

            int a = A[i], b = A[i+1];

            int high = Math.max(A[N-1] - K, a + K);

            int low = Math.min(A[0] + K, b - K);

            ans = Math.min(ans, high - low);

        }

        return ans;

    }

https://leetcode.com/problems/smallest-range-ii/discuss/173505/Java-Solution-with-the-Picture-to-explain-it

We can use greedy algorithm to solve this problem and the best status each time is bipartite, which means every element from left + K and every element from right - K. Firstly, we need to sort the Array. And, we can assume all the numbers array A - K. So, we can get the initial candidate. Then we increase the number of elements that + K and each status will update min & max and the candidate.

j = i + 1

  i j
  o----
----o
  ----o
     ----o
        ----o

    i j
  o----
    o----
  ----o
     ----o
        ----o
        
      i  j  
  o----
    o----
      o----
     ----o
        ----o


         i  j  
  o----
    o----
      o----
         o----
        ----o

    public int smallestRangeII(int[] A, int K) {
        Arrays.sort(A);
        int n = A.length;
        int res = A[n - 1] - A[0];
        for (int i = 0; i < n - 1; i++) {
            int max = Math.max(A[i] + K, A[n - 1] - K);
            int min = Math.min(A[i + 1] - K, A[0] + K);
            res = Math.min(res, max - min);
        }
        return res;
    }

https://leetcode.com/problems/smallest-range-ii/discuss/173389/simple-C%2B%2B-solution-with-explanation

• Sort the vector.
• Assuming there is a point, on the left of the point, all elements add K, on the right of the point, all elements substract K, check each possible point. (a point is between two numbers).

• Cause there are two segments (A[0]+K, A[1]+K, ..., A[i]+K, A[i+1]-K, ..., A[n]-K), the first one is on the left of the current point (A[i] + K is the last element of the first segment), the second one is on the right of the current point (A[i + 1] - K is the first element of the second segment). For the first segment, the smallest element is left, the largest is A[i] + K; For the second segment, A[i + 1] - K is the smallest element, the largest is right. Thus, for each point, the largest element should be either A[i] + K or right, the smallest element should be either left or A[i + 1] - K.

    int smallestRangeII(vector<int>& A, int K) {
        sort(A.begin(), A.end());
        int res = A[A.size() - 1] - A[0];
        int left = A[0] + K, right = A[A.size() - 1] - K;
        for (int i = 0; i < A.size() - 1; i++) {
            int maxi = max(A[i] + K, right), mini = min(left, A[i + 1] - K);
            res = min(res, maxi - mini);
        }
        return res;
    }

https://leetcode.com/problems/smallest-range-ii/discuss/173377/C%2B%2BJavaPython-Add-0-or-2-*-K

For each integer A[i],
we may choose either x = -K or x = K.

If we add K to all B[i], the result won't change.

It's the same as:
For each integer A[i], we may choose either x = 0 or x = 2 * K.

Explanation:

We sort the A first, and we choose to add x = 0 to all A[i].
Now we have res = A[n - 1] - A[0].
Starting from the smallest of A, we add 2 * K to A[i],
hoping this process will reduce the difference.

Update the new mx = max(mx, A[i] + 2 * K)
Update the new mn = min(A[i + 1], A[0] + 2 * K)
Update the res = min(res, mx - mn)

    public int smallestRangeII(int[] A, int K) {
        Arrays.sort(A);
        int n = A.length, mx = A[n - 1], mn = A[0], res = mx - mn;
        for (int i = 0; i < n - 1; ++i) {
            mx = Math.max(mx, A[i] + 2 * K);
            mn = Math.min(A[i + 1], A[0] + 2 * K);
            res = Math.min(res, mx - mn);
        }
        return res;
    }

Q: Do we have to sort the list?
A: In general cases, Yes. and this can be easily proved.

For example A = [0,1,4,5,6,7,8,9], K = 5
result = 2 * K - max(gap between numbers) = 2 * 5 - (4 - 1) = 7

To get the gap of consecutive numbers (in sorted order),
so in fact, this problem has no difference from 164. Maximum Gap

I don't have a better idea than sort.
But we don't have to use promitif O(NlogN) sort.
Other O(N) sort like bucket sort can be apllied to this problem.

Q: Except the general cases, do we any corner case?
A: Yes
if max(A) - min(A) >= 4 * K, return max(A) - min(A) - 2 * K
if max(A) - min(A) <= K, return max(A) - min(A)
Otherwise, we have to sort.

Q: Can we optimise this O(NlogN) solution?
A:
Optimization 1， Apply O(N) sort
Reference to 164. Maximum Gap.

Optimization 2， Sort only one part of whole list
To be easier understood, I sort the whole list here.
But we don't have to.
We can only take and sort he number between [max(A) - 2 * K, min(A) + 2 * K]

This will help improve the complexity a lot.
In 30 of 68 total cases, we solve the problem in O(N).
In ther rest cases, we solve in O(KlogK) where K <= N.

Example in python, it will improve from 120ms to 45ms.

    def smallestRangeII(self, A, K):
        ma, mi = max(A), min(A)
        if ma - mi >= 4 * K: return ma - mi - 2 * K
        if ma - mi <= K: return ma - mi
        inter = sorted([i for i in A if ma - 2 * K < i < mi + 2 * K] + [ma - 2 * K, mi + 2 * K])
        return min(a + 2 * K - b for a, b in zip(inter, inter[1:]))

https://leetcode.com/problems/smallest-range-ii/discuss/173471/JAVA-solution-very-easy-to-understand-sliding-window

    public int smallestRangeII(int[] A, int K) {
        if (A == null || A.length < 2) {
            return 0;
        }
        
        List<int[]> candidates = new ArrayList<int[]>();
        for (int i = 0; i < A.length; i++) {
            candidates.add(new int[]{i, A[i] - K});
            candidates.add(new int[]{i, A[i] + K});
        }
        
        // sliding window to let the window contains all indexes from A
        Collections.sort(candidates, (x1, x2) -> {
            return x1[1] < x2[1] ? -1 : 1;
        });
        
        int result = Integer.MAX_VALUE;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int left = 0, right = 0;
        while (right < candidates.size()) {
            // move right until contains all indexes
            while (right < candidates.size() && map.size() < A.length) {
                int index = candidates.get(right)[0];
                if (!map.containsKey(index)) {
                    map.put(index, 0);
                }
                map.put(index, map.get(index) + 1);
                right++;
            }
            
            int newRight = right;
            right--;
            
            // move left until has space to move right
            while (left < right && map.size() >= A.length) {
                result = Math.min(result, candidates.get(right)[1] - candidates.get(left)[1]);
                int index = candidates.get(left)[0];
                map.put(index, map.get(index) - 1);
                if (map.get(index) == 0) {
                    map.remove(index);
                }
                left++;
            }
            
            right = newRight;
        }
        return result;
    }




https://leetcode.com/problems/smallest-range-ii/discuss/174928/c%2B%2B-O(n)-time-solution!-Take-the-challenge!-With-very-very-detail-description-and-comments