LeetCode 908: Smallest Range I

Problem Restatement

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

For each index, we may change nums[i] by adding some integer x, where:

-k <= x <= k

Each index can be changed at most once.

After the changes, the score of the array is:

max(nums) - min(nums)

Return the minimum possible score. The official examples include [0, 10] with k = 2, where the answer is 6.

Input and Output

Function shape:

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

Examples

Example 1:

nums = [1]
k = 0

There is only one value, so the score is:

1 - 1 = 0

Answer:

0

Example 2:

nums = [0, 10]
k = 2

We can change the array to:

[2, 8]

The score is:

8 - 2 = 6

Answer:

6

Example 3:

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

We can make the values overlap around the same point.

One valid result is:

[4, 4, 4]

The score is:

0

Answer:

0

First Thought: Try All Adjustments

A direct approach is to try every possible change for every number.

For each nums[i], possible new values range from:

nums[i] - k

to:

nums[i] + k

Then we could test every combination and choose the smallest score.

This is not practical. The number of combinations grows too quickly.

We need to reason about the range directly.

Key Insight

Only the smallest and largest original values matter.

Let:

mn = min(nums)
mx = max(nums)

The original score is:

mx - mn

To minimize the score:

• Increase the smallest value as much as possible.
• Decrease the largest value as much as possible.

So the smallest value can become at most:

mn + k

The largest value can become at least:

mx - k

The new gap is:

(mx - k) - (mn + k)

which simplifies to:

mx - mn - 2 * k

But a score cannot be negative.

So the answer is:

max(0, mx - mn - 2 * k)

This is the standard mathematical solution for this problem.

Algorithm

1. Find the minimum value in nums.
2. Find the maximum value in nums.
3. Compute the original range:

mx - mn

4. Reduce it by 2 * k.
5. If the result is negative, return 0.

Correctness

Let mn be the minimum value and mx be the maximum value in the original array.

No value can increase by more than k, so the original minimum cannot be forced higher than mn + k.

No value can decrease by more than k, so the original maximum cannot be forced lower than mx - k.

Therefore, if the two adjusted extremes remain separated, the score cannot be smaller than:

(mx - k) - (mn + k)

The algorithm achieves this bound by increasing the minimum-side values and decreasing the maximum-side values as needed.

If the intervals overlap, then the values can be moved to a common overlapping range, so the score can be 0.

Since scores cannot be negative, the minimum possible score is:

max(0, mx - mn - 2 * k)

Therefore, the algorithm returns the optimal answer.

Complexity

Implementation

class Solution:
    def smallestRangeI(self, nums: list[int], k: int) -> int:
        mn = min(nums)
        mx = max(nums)

        return max(0, mx - mn - 2 * k)

Code Explanation

Find the smallest and largest values:

mn = min(nums)
mx = max(nums)

The original range is:

mx - mn

Each side can move inward by at most k, so the range can shrink by at most:

2 * k

Return the non-negative result:

return max(0, mx - mn - 2 * k)

Testing

def run_tests():
    s = Solution()

    assert s.smallestRangeI([1], 0) == 0
    assert s.smallestRangeI([0, 10], 2) == 6
    assert s.smallestRangeI([1, 3, 6], 3) == 0
    assert s.smallestRangeI([4, 8, 10], 1) == 4
    assert s.smallestRangeI([5, 5, 5], 10) == 0
    assert s.smallestRangeI([1, 100], 10) == 79

    print("all tests passed")

run_tests()

Test meaning: