Formatted question description: https://leetcode.ca/all/910.html

910. Smallest Range II

Level

Medium

Description

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]

Note:

  1. 1 <= A.length <= 10000
  2. 0 <= A[i] <= 10000
  3. 0 <= K <= 10000

Solution

First sort the array A, find the maximum element and the minimum element and calculate the difference.

Next consider whether each number should be added K or -K. For any two numbers num1 and num2, if num1 < num2, then adding K to num1 and adding -K to num2 is always optimal.

After A is sorted, find the maximum index i such that A[i] should be added K, and the minimum difference can be obtained.

  • class Solution {
    public int smallestRangeII(int[] A, int K) {
        Arrays.sort(A);
        int length = A.length;
        int min = A[0], max = A[length - 1];
        int difference = max - min;
        for (int i = 1; i < length; i++) {
            int num1 = A[i - 1], num2 = A[i];
            int high = Math.max(A[length - 1] - K, num1 + K);
            int low = Math.min(A[0] + K, num2 - K);
            difference = Math.min(difference, high - low);
        }
        return difference;
    }
}

  • Todo

  • class Solution(object):
    def smallestRangeII(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        A.sort()
        N = len(A)
        mn, mx = A[0], A[-1]
        res = mx - mn
        for i in range(N - 1):
            mx = max(A[i] + 2 * K, mx)
            mn = min(A[i + 1], A[0] + 2 * K)
            res = min(mx - mn, res)
        return res

All Problems

All Solutions