Massive Algorithms: LeetCode 910

LeetCode 910 - 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

LeetCode 910 - Smallest Range II

Explanation:

Labels

Popular Posts