# 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:

```python
-k <= x <= k
```

Each index can be changed at most once.

After the changes, the score of the array is:

```python
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

| Item | Meaning |
|---|---|
| Input | Integer array `nums` and integer `k` |
| Output | Minimum possible score |
| Operation | Add any integer from `[-k, k]` to each element |
| Score | Maximum value minus minimum value after changes |

Function shape:

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

## Examples

Example 1:

```python
nums = [1]
k = 0
```

There is only one value, so the score is:

```python
1 - 1 = 0
```

Answer:

```python
0
```

Example 2:

```python
nums = [0, 10]
k = 2
```

We can change the array to:

```python
[2, 8]
```

The score is:

```python
8 - 2 = 6
```

Answer:

```python
6
```

Example 3:

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

We can make the values overlap around the same point.

One valid result is:

```python
[4, 4, 4]
```

The score is:

```python
0
```

Answer:

```python
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:

```python
nums[i] - k
```

to:

```python
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:

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

The original score is:

```python
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:

```python
mn + k
```

The largest value can become at least:

```python
mx - k
```

The new gap is:

```python
(mx - k) - (mn + k)
```

which simplifies to:

```python
mx - mn - 2 * k
```

But a score cannot be negative.

So the answer is:

```python
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:

```python
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:

```python
(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:

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

Therefore, the algorithm returns the optimal answer.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | We scan the array to find `min` and `max` |
| Space | `O(1)` | Only a few variables are used |

## Implementation

```python
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:

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

The original range is:

```python
mx - mn
```

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

```python
2 * k
```

Return the non-negative result:

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

## Testing

```python
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:

| Test | Why |
|---|---|
| `[1]`, `k = 0` | Single value has score `0` |
| `[0, 10]`, `k = 2` | Main sample with nonzero answer |
| `[1, 3, 6]`, `k = 3` | Values can overlap to score `0` |
| `[4, 8, 10]`, `k = 1` | Range shrinks but stays positive |
| `[5, 5, 5]`, `k = 10` | Already zero range |
| `[1, 100]`, `k = 10` | Large gap remains after shrinking |