Minimize the Max-Min Gap of an Array After Changing Up to Three Elements

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

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

Input: nums = [9, 2, 7, 4]
Output: 0

Change 9, 2 and 7 to 4; every value is then equal.

Example 2

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

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.