Minimize the Max-Min Gap of an Array After Changing Up to Three Elements
Company: DRW
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given an integer array `nums`. You may change the values of at most three of its elements, setting each changed element to any integer you like. Return the smallest possible difference between the largest and the smallest value in the array after the changes.
### Function Signature
```python
def min_range_after_three_changes(nums: list[int]) -> int:
```
### Rules
- Choose up to three positions and set each one to any integer, independently. Changing fewer than three elements, or none, is allowed.
- Elements are changed, never removed: the array keeps its length.
- Return the minimum, over all allowed changes, of `max(nums) - min(nums)` for the modified array.
### Constraints
- `1 <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
### Examples
**Example 1**
```text
Input: nums = [9, 2, 7, 4]
Output: 0
```
Change `9`, `2` and `7` to `4`; every value is then equal.
**Example 2**
```text
Input: nums = [20, 75, 81, 82, 95]
Output: 1
```
Change `20`, `75` and `95` to `81`. The array becomes `[81, 81, 81, 82, 81]`, whose largest and smallest values differ by `1`. No set of three changes can make all five values equal, because `81` and `82` cannot both stay.
**Example 3**
```text
Input: nums = [6, 6, 0, 1, 1, 4, 6]
Output: 2
```
Change `0`, `1` and `1` to `6`. The array becomes `[6, 6, 6, 6, 6, 4, 6]`, and `6 - 4 = 2`.
Overview: Given an integer array, you may change up to three elements to any values; return the smallest possible difference between the largest and smallest values afterward. It tests reasoning about which extreme values are worth changing and careful handling of short arrays.
Read the full DRW Software Engineer interview experience this question came from
You are given an integer array `nums`. You may change the values of at most three of its elements, setting each changed element to any integer you like. Return the smallest possible difference between the largest and the smallest value in the array after the changes.
Implement `min_range_after_three_changes(nums)`.
### Rules
- Choose up to three positions and set each one to any integer, independently. Changing fewer than three elements, or none, is allowed.
- Elements are changed, never removed: the array keeps its length.
- Return the minimum, over all allowed changes, of `max(nums) - min(nums)` for the modified array.
### Constraints
- `1 <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
The answer is an integer between `0` and `2 * 10^9`. The Java and C++ signatures return a 64-bit integer (`long` / `long long`).
### Examples
**Example 1**
```text
Input: nums = [9, 2, 7, 4]
Output: 0
```
Change `9`, `2` and `7` to `4`; every value is then equal.
**Example 2**
```text
Input: nums = [20, 75, 81, 82, 95]
Output: 1
```
Change `20`, `75` and `95` to `81`. The array becomes `[81, 81, 81, 82, 81]`, whose largest and smallest values differ by `1`. No set of three changes can make all five values equal, because at least two of the five distinct values must stay unchanged.
Constraints
- 1 <= len(nums) <= 10^5
- -10^9 <= nums[i] <= 10^9
Examples
Input: ([5],)
Expected Output: 0
Explanation: Singleton: a single value already has range 0.
Input: ([-1000000000, 1000000000],)
Expected Output: 0
Explanation: Length 2 at both value extremes: change one element to equal the other.
Hints
- A changed element can be set to any integer, so it never has to fall outside the range of the elements you leave unchanged.
- Changing an element never makes the range larger, so think about how few values must stay unchanged, especially for very short arrays.
- Ask which of the original values could still be the largest or the smallest after the changes.