910. Smallest Range II

Problem

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

Problem Summary

Given an integer array A, for each integer A[i], you can choose x = -K or x = K (K is always a non-negative integer), and add x to A[i]. After this process, array B is obtained. Return the smallest possible difference between the maximum value of B and the minimum value of B.

Solution Explanation

• Easy problem. First sort the array and find the largest difference in array A. Then scan through the array once, using two pointers, choosing x = -K or x = K. Each choice updates the smallest difference between the maximum and minimum values. After one pass, the answer that satisfies the problem can be found.

Code

package leetcode

import "sort"

func smallestRangeII(A []int, K int) int {
	n := len(A)
	sort.Ints(A)
	res := A[n-1] - A[0]
	for i := 0; i < n-1; i++ {
		a, b := A[i], A[i+1]
		high := max(A[n-1]-K, a+K)
		low := min(A[0]+K, b-K)
		res = min(res, high-low)
	}
	return res
}

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
}