Minimum number of swaps required to minimize sum of absolute differences between adjacent array elements | Java program for the above approach ; Pair class ; Function to find the minimum number of swaps required to sort the array in increasing order ; Stores the array elements with its index ; Sort the array in the increasing order ; Keeps the track of visited elements ; Stores the count of swaps required ; Traverse array elements ; If the element is already swapped or at correct position ; Find out the number of nodes in this cycle ; Update the value of j ; Move to the next element ; Increment cycle_size ; Update the ans by adding current cycle ; Function to find the minimum number of swaps required to sort the array in decreasing order ; Stores the array elements with its index ; Sort the array in the descending order ; Keeps track of visited elements ; Stores the count of resultant swap required ; Traverse array elements ; If the element is already swapped or at correct position ; Find out the number of node in this cycle ; Update the value of j ; Move to the next element ; Increment the cycle_size ; Update the ans by adding current cycle size ; Function to find minimum number of swaps required to minimize the sum of absolute difference of adjacent elements ; Sort in ascending order ; Sort in descending order ; Return the minimum value ; Driver code
import java . lang . * ; import java . util . * ; class pair { int first , second ; pair ( int first , int second ) { this . first = first ; this . second = second ; } } class GFG { static int minSwapsAsc ( int [ ] arr , int n ) { pair [ ] arrPos = new pair [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { arrPos [ i ] = new pair ( arr [ i ] , i ) ; } Arrays . sort ( arrPos , ( a , b ) -> a . first - b . first ) ; boolean [ ] vis = new boolean [ n ] ; int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( vis [ i ] arrPos [ i ] . second == i ) continue ; int cycle_size = 0 ; int j = i ; while ( ! vis [ j ] ) { vis [ j ] = true ; j = arrPos [ j ] . second ; cycle_size ++ ; } if ( cycle_size > 0 ) { ans += ( cycle_size - 1 ) ; } } return ans ; } static int minSwapsDes ( int [ ] arr , int n ) { pair [ ] arrPos = new pair [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { arrPos [ i ] = new pair ( arr [ i ] , i ) ; } Arrays . sort ( arrPos , ( a , b ) -> b . first - a . first ) ; boolean [ ] vis = new boolean [ n ] ; int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( vis [ i ] arrPos [ i ] . second == i ) continue ; int cycle_size = 0 ; int j = i ; while ( ! vis [ j ] ) { vis [ j ] = true ; j = arrPos [ j ] . second ; cycle_size ++ ; } if ( cycle_size > 0 ) { ans += ( cycle_size - 1 ) ; } } return ans ; } static int minimumSwaps ( int [ ] arr ) { int S1 = minSwapsAsc ( arr , arr . length ) ; int S2 = minSwapsDes ( arr , arr . length ) ; return Math . min ( S1 , S2 ) ; } public static void main ( String [ ] args ) { int [ ] arr = { 3 , 4 , 2 , 5 , 1 } ; System . out . println ( minimumSwaps ( arr ) ) ; } }