Ruta más corta para recorrer todos los elementos de una array circular en orden creciente

Hay N enteros distintos dispuestos en un círculo. La distancia entre dos números adyacentes es 1 . La tarea es viajar en este círculo comenzando con el número más pequeño, luego pasando al segundo más pequeño, al tercero más pequeño, y así sucesivamente hasta el número más grande e imprimir la distancia mínima de viaje.
Ejemplos: 

Entrada: arr[] = {3, 6, 5, 1, 2, 4} 
Salida: 8 
1 -> 2 (de izquierda a derecha) 
2 -> 3 (de izquierda a derecha) 
3 -> 4 (de derecha a izquierda) 
4 -> 5 (De izquierda a derecha o de derecha a izquierda) 
5 -> 6 (De derecha a izquierda)
Entrada: arr[] = {14, 16, 8, 17, 12, 10, 4, 13, 11, 20} 
Salida: 27 

Planteamiento: Si queremos viajar entre dos elementos con índices i y j , tenemos dos caminos posibles, uno de longitud |i – j| y el otro de longitud n – |i – j| y tomaremos el que tenga la distancia mínima. 
Inicialmente, construimos una array de pares de (elemento, índice) y la clasificamos en orden creciente de elementos. Entonces podemos tomar cada dos pares consecutivos y encontrar el camino más corto para viajar entre estos dos elementos.
A continuación se muestra la implementación del enfoque anterior:  

#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
 
// Function to return the minimum distance
int min_distance(int n, vector<int> arr)
{
 
    // Declare a Pair[] array of size n
    vector<pair<int,int>> val(n);
 
    // Store all the (element, index) pairs
    for ( int i = 0; i < n; i++)
        val[i] = {arr[i], i};
 
    // Sort the pairs in ascending order of the value
    sort(val.begin(), val.end());
 
    int min_dist = 0;
    for (int i = 1; i < n; i++)
    {
 
        // Choose the minimum distance path
        // of the two available
        min_dist += min(abs(val[i].second - val[i - 1].second),
                    n - abs(val[i].second - val[i - 1].second));
    }
 
    return min_dist;
}
 
 
// Driver Code
int main()
{
    vector<int> arr = {3, 6, 5, 1, 2, 4};
    int n = arr.size();
    cout << (min_distance(n, arr));
}
 
// This code is contributed by mohit kumar 29

// Java implementation of the approach
import java.util.*;
 
class GFG {
 
    // Function to return the minimum distance
    static int min_distance(int n, int[] arr)
    {
 
        // Declare a Pair[] array of size n
        Pair[] val = new Pair[n];
 
        // Store all the (element, index) pairs
        for (int i = 0; i < n; i++)
            val[i] = new Pair(arr[i], i);
 
        // Sort the pairs in ascending order of the value
        Arrays.sort(val, com);
 
        int min_dist = 0;
        for (int i = 1; i < n; i++) {
 
            // Choose the minimum distance path
            // of the two available
            min_dist
                += Math.min(Math.abs(val[i].y - val[i - 1].y),
                            n - Math.abs(val[i].y - val[i - 1].y));
        }
 
        return min_dist;
    }
 
    // Comparator to be used in the
    // sorting of pairs based on the values
    static final Comparator<Pair> com = new Comparator<Pair>() {
        public int compare(Pair a, Pair b)
        {
            if (Integer.compare(a.x, b.x) != 0)
                return Integer.compare(a.x, b.x);
            else
                return Integer.compare(a.y, b.y);
        }
    };
 
    // Class to represent a pair
    static class Pair {
        int x, y;
        Pair(int p, int q)
        {
            x = p;
            y = q;
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int[] arr = new int[] { 3, 6, 5, 1, 2, 4 };
        int n = arr.length;
 
        System.out.println(min_distance(n, arr));
    }
}

# Python implementation of the approach
 
# Function to return the minimum distance
def min_distance(n, arr):
     
    # Declare a Pair[] array of size n
    val = [None] * n
 
    # Store all the (element, index) pairs
    for i in range(0, n):
        val[i] = (arr[i], i)
 
    # Sort the pairs in ascending order of the value
    val.sort()
 
    min_dist = 0
    for i in range(1, n):
 
        # Choose the minimum distance path
        # of the two available
        min_dist += min(abs(val[i][1] - val[i - 1][1]),
                        n - abs(val[i][1] - val[i - 1][1]))
         
    return min_dist
 
# Driver code
if __name__ == "__main__":
     
    arr = [3, 6, 5, 1, 2, 4]
    n = len(arr)
 
    print(min_distance(n, arr))
 
# This code is contributed by Rituraj Jain

<script>
 
// JavaScript implementation of the approach
 
// Function to return the minimum distance
function min_distance(n,arr)
{
    // Declare a Pair[] array of size n
        let val = new Array(n);
      
        // Store all the (element, index) pairs
        for (let i = 0; i < n; i++)
            val[i] = [arr[i], i];
  
        // Sort the pairs in ascending order of the value
        val.sort(function(a,b){return a[0]-b[0];});
  
        let min_dist = 0;
        for (let i = 1; i < n; i++) {
  
            // Choose the minimum distance path
            // of the two available
            min_dist
                += Math.min(Math.abs(val[i][1] - val[i - 1][1]),
                         n - Math.abs(val[i][1] - val[i - 1][1]));
        }
  
        return min_dist;
}
 
// Driver code
let arr=[3, 6, 5, 1, 2, 4];
let n=arr.length;
document.write(min_distance(n, arr))
 
// This code is contributed by patel2127
 
</script>

8

Complejidad de tiempo: O(n * log(n))

Espacio Auxiliar: O(n)