Welcome to Subscribe On Youtube

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.

• Java
• Python
• C++
• Go

• 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;
      }
  }
  

• class Solution:
      def smallestRangeII(self, nums: List[int], k: int) -> int:
          nums.sort()
          ans = nums[-1] - nums[0]
          for i in range(1, len(nums)):
              mi = min(nums[0] + k, nums[i] - k)
              mx = max(nums[i - 1] + k, nums[-1] - k)
              ans = min(ans, mx - mi)
          return ans
  
  ############
  
  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
  

• class Solution {
  public:
      int smallestRangeII(vector<int>& nums, int k) {
          sort(nums.begin(), nums.end());
          int n = nums.size();
          int ans = nums[n - 1] - nums[0];
          for (int i = 1; i < n; ++i) {
              int mi = min(nums[0] + k, nums[i] - k);
              int mx = max(nums[i - 1] + k, nums[n - 1] - k);
              ans = min(ans, mx - mi);
          }
          return ans;
      }
  };
  

• func smallestRangeII(nums []int, k int) int {
  	sort.Ints(nums)
  	n := len(nums)
  	ans := nums[n-1] - nums[0]
  	for i := 1; i < n; i++ {
  		mi := min(nums[0]+k, nums[i]-k)
  		mx := max(nums[i-1]+k, nums[n-1]-k)
  		ans = min(ans, mx-mi)
  	}
  	return ans
  }
  
  func max(a, b int) int {
  	if a > b {
  		return a
  	}
  	return b
  }
  
  func min(a, b int) int {
  	if a < b {
  		return a
  	}
  	return b
  }
  

All Problems

All Solutions