Минимизируйте максимальную разницу между любой парой элементов массива ровно на одно удаление

Дан массив arr[] , состоящий из N целых чисел (N > 2), задача состоит в том, чтобы минимизировать максимальную разницу между любой парой элементов (arr[i], arr[j]) , удалив ровно один элемент.

Примеры:

Input: arr[] = {1, 3, 4, 7}
Output: 3
Explanation:
Removing the element 7 from array, modifies the array  to {1, 3, 4}.
Here (4, 1) has difference = 4 – 1 = 3 which is minimum possible maximum difference. 

Input: arr[] = {1, 2, 3, 4}
Output: 2

Наивный подход: самый простой подход к решению данной проблемы - удалить каждый элемент один за другим и проверить, какой элемент дает минимальную максимальную разницу между каждой парой элементов.

Временная сложность: O(N ³ )
Вспомогательное пространство: O(N)

Эффективный подход. Приведенный выше подход также можно оптимизировать, если учесть тот факт, что максимальная разница равна разнице между максимальным и минимальным элементом данного массива. Таким образом, удаление максимального элемента или удаление минимального элемента всегда дает оптимальный ответ.

Поэтому идея состоит в том, чтобы отсортировать данный массив в порядке возрастания и вывести в качестве результата минимум значения (arr[N – 2] – arr[0]) и (arr[N – 1] – arr[1]) . минимальная максимальная разница.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (N * log N)
Вспомогательное пространство: O(N)