LeetCode 910: Smallest Range II

Problem Restatement

We are given an integer array nums and an integer k.

For every index i, we must either:

nums[i] + k

or:

nums[i] - k

Return the minimum possible difference between the maximum and minimum values after all choices are made.

Unlike the previous problem, every number must choose exactly one of the two operations.

Input and Output

Function shape:

def smallestRangeII(nums: list[int], k: int) -> int:
    ...

Examples

Example 1:

nums = [1]
k = 0

The array stays:

[1]

Range:

1 - 1 = 0

Answer:

0

Example 2:

nums = [0, 10]
k = 2

Possible transformation:

[2, 8]

Range:

8 - 2 = 6

Answer:

6

Example 3:

nums = [1, 3, 6]
k = 3

One optimal transformation is:

[4, 6, 3]

Sorted result:

[3, 4, 6]

Range:

6 - 3 = 3

Answer:

3

The official examples use these exact results. (leetcode.com)

First Thought: Try Every Combination

For each number, we have two choices:

+k

or:

-k

So with n numbers, there are:

2^n

possible arrays.

Trying all combinations is impossible for large n.

We need to exploit structure in the problem.

Key Insight

Sort the array first.

Suppose:

nums = [1, 3, 6]
k = 3

After sorting, imagine splitting the array into two parts.

• Left part gets +k
• Right part gets -k

For example:

[1]       -> +3
[3, 6]    -> -3

becomes:

[4, 0, 3]

The important insight is:

After sorting, there is always an optimal solution where all smaller elements use +k and all larger elements use -k.

We only need to try every split point.

What Can Become the Minimum or Maximum?

After sorting:

nums[0] <= nums[1] <= ... <= nums[n - 1]

Suppose split position i means:

• nums[0..i] use +k
• nums[i+1..n-1] use -k

Then:

Largest possible value:

max(nums[i] + k, nums[n - 1] - k)

Smallest possible value:

min(nums[0] + k, nums[i + 1] - k)

So the range is:

high - low

We try every split and take the minimum.

Algorithm

1. Sort the array.
2. Initialize the answer as the original range.
3. For every split position i:
   • Left side uses +k
   • Right side uses -k
4. Compute:
   • New maximum
   • New minimum
   • Their difference
5. Keep the smallest difference.

Correctness

Let the sorted array be:

nums[0] <= nums[1] <= ... <= nums[n - 1]

Consider any valid assignment of +k and -k.

Suppose there exist indices a < b such that:

• nums[a] uses -k
• nums[b] uses +k

Since:

nums[a] <= nums[b]

swapping their choices cannot increase the range:

• Increasing the larger value even more is not helpful.
• Decreasing the smaller value even more is not helpful.

By repeatedly applying this exchange argument, every optimal solution can be transformed into one where:

• Smaller values use +k
• Larger values use -k

So an optimal solution always corresponds to some split point.

For a chosen split:

• The maximum value must be either:

  • the largest boosted left value
  • or the largest reduced right value

• The minimum value must be either:

  • the smallest boosted left value
  • or the smallest reduced right value

The algorithm checks all such splits and computes the resulting range exactly.

Therefore, it returns the minimum possible range.

Complexity

Implementation

class Solution:
    def smallestRangeII(self, nums: list[int], k: int) -> int:
        nums.sort()

        n = len(nums)

        answer = nums[-1] - nums[0]

        for i in range(n - 1):
            high = max(nums[i] + k, nums[-1] - k)
            low = min(nums[0] + k, nums[i + 1] - k)

            answer = min(answer, high - low)

        return answer

Code Explanation

First sort the array:

nums.sort()

Without sorting, we cannot reason about split positions.

The original range is one candidate answer:

answer = nums[-1] - nums[0]

Now try every split:

for i in range(n - 1):

Left side:

nums[0..i]

gets +k.

Right side:

nums[i+1..n-1]

gets -k.

The largest value becomes:

high = max(nums[i] + k, nums[-1] - k)

The smallest value becomes:

low = min(nums[0] + k, nums[i + 1] - k)

Update the best answer:

answer = min(answer, high - low)

Testing

def run_tests():
    s = Solution()

    assert s.smallestRangeII([1], 0) == 0
    assert s.smallestRangeII([0, 10], 2) == 6
    assert s.smallestRangeII([1, 3, 6], 3) == 3
    assert s.smallestRangeII([7, 8, 8], 5) == 1
    assert s.smallestRangeII([2, 7, 2], 1) == 3
    assert s.smallestRangeII([1, 10], 5) == 1

    print("all tests passed")

run_tests()

Test meaning: