MNR - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You are given an array A, from which you can delete at most two elements.
Find the minimum possible value of \max(A) - \min(A).

EXPLANATION:

It’s ideal to only delete elements that actually do change either \min(A) or \max(A).
In other words, it’s ideal to only delete either \min(A) or \max(A) themselves.

Since we delete twice, there are three possibilities:

  1. Delete \min(A) twice.
  2. Delete \max(A) twice.
  3. Delete \min(A) once and \max(A) once.

Simply try all three cases and take the best among them.

An easy way to implement this is with the help of sorting.
Suppose A_1 \leq A_2 \leq \ldots \leq A_N.
Then,

  • Deleting the two largest elements means deleting A_N and A_{N-1}.
    The range of the remaining elements is A_{N-2} - A_1.
  • Deleting the two smallest elements means deleting A_1 and A_2.
    The range of the remaining elements is A_N - A_3.
  • Deleting the largest and smallest element once each makes the range A_{N-1} - A_2.

So, after sorting the array, the output is simply

\min(A_N - A_3, A_{N-1} - A_2, A_{N-2} - A_1)

It is, of course, possible to implement each case in linear time without sorting - it just becomes a lot more code.

TIME COMPLEXITY:

\mathcal{O}(N) or \mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()

    ans = min(a[n-1] - a[2], a[n-2] - a[1], a[n-3] - a[0])
    print(ans)