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

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

Примеры:

Input: arr[] = {8, 50, 11, 2}
Output: 2
Explanation:
Operation 1: Swapping of elements 8 and 2, modifies the array arr[] to {2, 50, 11, 8}.
Operation 2: Swapping of elements 8 and 50, modifies the array arr[] to {2, 8, 11, 50}.
The sum of absolute difference of adjacent elements of the modified array is 48, which is minimum.
Therefore, the minimum number of swaps required is 2. 

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

Подход: Данная задача может быть решена на основе наблюдения, что сумма абсолютной разности соседних элементов будет минимальной, если массив отсортирован либо в возрастающем, либо в убывающем порядке. Следуйте инструкциям, чтобы решить проблему.

• Найдите минимальное количество свопов, необходимых для сортировки заданного массива в порядке возрастания, используя подход, обсуждаемый в этой статье. Пусть счет будет S1 .
• Найдите минимальное количество свопов, необходимых для сортировки заданного массива в порядке убывания, используя подход, обсуждаемый в этой статье. Пусть счет будет S2 .
• После выполнения вышеуказанных шагов выведите минимум значений S1 и S2 как результирующее минимальное количество требуемых свопов.

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

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