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

```python
nums[i] + k
```

or:

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

| Item | Meaning |
|---|---|
| Input | Integer array `nums` and integer `k` |
| Output | Minimum possible range after modifications |
| Allowed operations | Add `k` or subtract `k` from every element |
| Goal | Minimize `max(nums) - min(nums)` |

Function shape:

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

## Examples

Example 1:

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

The array stays:

```python
[1]
```

Range:

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

Answer:

```python
0
```

Example 2:

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

Possible transformation:

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

Range:

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

Answer:

```python
6
```

Example 3:

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

One optimal transformation is:

```python
[4, 6, 3]
```

Sorted result:

```python
[3, 4, 6]
```

Range:

```python
6 - 3 = 3
```

Answer:

```python
3
```

The official examples use these exact results. ([leetcode.com](https://leetcode.com/problems/smallest-range-ii/?utm_source=chatgpt.com))

## First Thought: Try Every Combination

For each number, we have two choices:

```python
+k
```

or:

```python
-k
```

So with `n` numbers, there are:

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

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

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

becomes:

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

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

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

Smallest possible value:

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

So the range is:

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

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

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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | Sorting dominates |
| Space | `O(1)` extra | Ignoring sorting internals |

## Implementation

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

```python
nums.sort()
```

Without sorting, we cannot reason about split positions.

The original range is one candidate answer:

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

Now try every split:

```python
for i in range(n - 1):
```

Left side:

```python
nums[0..i]
```

gets `+k`.

Right side:

```python
nums[i+1..n-1]
```

gets `-k`.

The largest value becomes:

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

The smallest value becomes:

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

Update the best answer:

```python
answer = min(answer, high - low)
```

## Testing

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

| Test | Why |
|---|---|
| `[1]`, `k = 0` | Single value |
| `[0, 10]`, `k = 2` | Main sample |
| `[1, 3, 6]`, `k = 3` | Mixed optimal split |
| Duplicate values | Checks equal elements |
| Unsorted input | Confirms sorting logic |
| Large adjustment | Range becomes very small |