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