PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You have an array A.
You can change at most one element.
Minimize \max(A) - \min(A).
EXPLANATION:
If we change neither \max(A) nor \min(A), then the value of \max(A) - \min(A) won’t change.
So we should change one of them to try and improve the answer.
Suppose we change \min(A).
This means \max(A) won’t change - as long as we don’t make the new element larger than \max(A).
So one option is to change \min(A) equal to \max(A).
After this change, the new minimum element of the array will be the second smallest element of the original array.
So, the score of the new array is \max(A) - \text{second\_min}(A).
Similarly, if we change \max(A), it’s best to change it to \min(A), in which case the score will be \text{second\_max}(A) - \min(A).
The overall answer is the smaller of the two options.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
a.sort()
print(min(a[-2] - a[0], a[-1] - a[1]))