Given an array arr[] consisting of N distinct positive integers, the task is to find the minimum number of elements required to be swapped to minimize the sum of absolute difference of each pair of adjacent elements.
Examples:
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
Approach: The given problem can be solved based on the observation that the sum of the absolute difference of adjacent elements will be minimum if the array is either sorted in increasing or decreasing order. Follow the steps to solve the problem.
- Find the minimum number of swaps required to sort the array given array in ascending order using the approach discussed in this article. Let the count be S1.
- Find the minimum number of swaps required to sort the array given array in descending order using the approach discussed in this article. Let the count be S2.
- After completing the above steps, print the minimum of the value S1 and S2 as the resultant minimum number of swaps required.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Comparator to sort in the descending// orderbool mycmp(pair<int, int> a, pair<int, int> b){ return a.first > b.first;}// Function to find the minimum number// of swaps required to sort the array// in increasing orderint minSwapsAsc(vector<int> arr, int n){ // Stores the array elements with // its index pair<int, int> arrPos[n]; for (int i = 0; i < n; i++) { arrPos[i].first = arr[i]; arrPos[i].second = i; } // Sort the array in the // increasing order sort(arrPos, arrPos + n); // Keeps the track of // visited elements vector<bool> vis(n, false); // Stores the count of swaps required int ans = 0; // Traverse array elements for (int i = 0; i < n; i++) { // If the element is already // swapped or at correct position if (vis[i] || arrPos[i].second == i) continue; // Find out the number of // nodes in this cycle int cycle_size = 0; // Update the value of j int j = i; while (!vis[j]) { vis[j] = 1; // Move to the next element j = arrPos[j].second; // Increment cycle_size cycle_size++; } // Update the ans by adding // current cycle if (cycle_size > 0) { ans += (cycle_size - 1); } } return ans;}// Function to find the minimum number// of swaps required to sort the array// in decreasing orderint minSwapsDes(vector<int> arr, int n){ // Stores the array elements with // its index pair<int, int> arrPos[n]; for (int i = 0; i < n; i++) { arrPos[i].first = arr[i]; arrPos[i].second = i; } // Sort the array in the // descending order sort(arrPos, arrPos + n, mycmp); // Keeps track of visited elements vector<bool> vis(n, false); // Stores the count of resultant // swap required int ans = 0; // Traverse array elements for (int i = 0; i < n; i++) { // If the element is already // swapped or at correct // position if (vis[i] || arrPos[i].second == i) continue; // Find out the number of // node in this cycle int cycle_size = 0; // Update the value of j int j = i; while (!vis[j]) { vis[j] = 1; // Move to the next element j = arrPos[j].second; // Increment the cycle_size cycle_size++; } // Update the ans by adding // current cycle size if (cycle_size > 0) { ans += (cycle_size - 1); } } return ans;}// Function to find minimum number of// swaps required to minimize the sum// of absolute difference of adjacent// elementsint minimumSwaps(vector<int> arr){ // Sort in ascending order int S1 = minSwapsAsc(arr, arr.size()); // Sort in descending order int S2 = minSwapsDes(arr, arr.size()); // Return the minimum value return min(S1, S2);}// Drive Codeint main(){ vector<int> arr{ 3, 4, 2, 5, 1 }; cout << minimumSwaps(arr); return 0;} |
Java
// Java program for the above approachimport java.lang.*;import java.util.*;// Pair classclass pair{ int first, second; pair(int first, int second) { this.first = first; this.second = second; }}class GFG{// Function to find the minimum number// of swaps required to sort the array// in increasing orderstatic int minSwapsAsc(int[] arr, int n){ // Stores the array elements with // its index pair[] arrPos = new pair[n]; for(int i = 0; i < n; i++) { arrPos[i] = new pair(arr[i], i); } // Sort the array in the // increasing order Arrays.sort(arrPos, (a, b)-> a.first - b.first); // Keeps the track of // visited elements boolean[] vis= new boolean[n]; // Stores the count of swaps required int ans = 0; // Traverse array elements for(int i = 0; i < n; i++) { // If the element is already // swapped or at correct position if (vis[i] || arrPos[i].second == i) continue; // Find out the number of // nodes in this cycle int cycle_size = 0; // Update the value of j int j = i; while (!vis[j]) { vis[j] = true; // Move to the next element j = arrPos[j].second; // Increment cycle_size cycle_size++; } // Update the ans by adding // current cycle if (cycle_size > 0) { ans += (cycle_size - 1); } } return ans;}// Function to find the minimum number// of swaps required to sort the array// in decreasing orderstatic int minSwapsDes(int[] arr, int n){ // Stores the array elements with // its index pair[] arrPos = new pair[n]; for(int i = 0; i < n; i++) { arrPos[i] = new pair(arr[i], i); } // Sort the array in the // descending order Arrays.sort(arrPos, (a, b)-> b.first - a.first); // Keeps track of visited elements boolean[] vis = new boolean[n]; // Stores the count of resultant // swap required int ans = 0; // Traverse array elements for(int i = 0; i < n; i++) { // If the element is already // swapped or at correct // position if (vis[i] || arrPos[i].second == i) continue; // Find out the number of // node in this cycle int cycle_size = 0; // Update the value of j int j = i; while (!vis[j]) { vis[j] = true; // Move to the next element j = arrPos[j].second; // Increment the cycle_size cycle_size++; } // Update the ans by adding // current cycle size if (cycle_size > 0) { ans += (cycle_size - 1); } } return ans;}// Function to find minimum number of// swaps required to minimize the sum// of absolute difference of adjacent// elementsstatic int minimumSwaps(int[] arr){ // Sort in ascending order int S1 = minSwapsAsc(arr, arr.length); // Sort in descending order int S2 = minSwapsDes(arr, arr.length); // Return the minimum value return Math.min(S1, S2);}// Driver codepublic static void main(String[] args){ int[] arr = { 3, 4, 2, 5, 1 }; System.out.println(minimumSwaps(arr));}}// This code is contributed by offbeat |
Python3
# Python3 program for the above approach# Function to find the minimum number# of swaps required to sort the array# in increasing orderdef minSwapsAsc(arr, n): # Stores the array elements with # its index arrPos = [[arr[i], i] for i in range(n)] # Sort the array in the # increasing order arrPos = sorted(arrPos) # Keeps the track of # visited elements vis = [False] * (n) # Stores the count of swaps required ans = 0 # Traverse array elements for i in range(n): # If the element is already # swapped or at correct position if (vis[i] or arrPos[i][1] == i): continue # Find out the number of # nodes in this cycle cycle_size = 0 # Update the value of j j = i while (not vis[j]): vis[j] = 1 # Move to the next element j = arrPos[j][1] # Increment cycle_size cycle_size += 1 # Update the ans by adding # current cycle if (cycle_size > 0): ans += (cycle_size - 1) return ans# Function to find the minimum number# of swaps required to sort the array# in decreasing orderdef minSwapsDes(arr, n): # Stores the array elements with # its index arrPos = [[0, 0] for i in range(n)] for i in range(n): arrPos[i][0] = arr[i] arrPos[i][1] = i # Sort the array in the # descending order arrPos = sorted(arrPos)[::-1] # Keeps track of visited elements vis = [False] * n # Stores the count of resultant # swap required ans = 0 # Traverse array elements for i in range(n): # If the element is already # swapped or at correct # position if (vis[i] or arrPos[i][1] == i): continue # Find out the number of # node in this cycle cycle_size = 0 # Update the value of j j = i while (not vis[j]): vis[j] = 1 # Move to the next element j = arrPos[j][1] # Increment the cycle_size cycle_size += 1 # Update the ans by adding # current cycle size if (cycle_size > 0): ans += (cycle_size - 1) return ans# Function to find minimum number of# swaps required to minimize the sum# of absolute difference of adjacent# elementsdef minimumSwaps(arr): # Sort in ascending order S1 = minSwapsAsc(arr, len(arr)) # Sort in descending order S2 = minSwapsDes(arr, len(arr)) # Return the minimum value return min(S1, S2)# Drive Codeif __name__ == '__main__': arr = [ 3, 4, 2, 5, 1 ] print (minimumSwaps(arr))# This code is contributed by mohit kumar 29 |
C#
// C# code to implement the approachusing System;// Pair classclass Pair { public int First { get; set; } public int Second { get; set; } public Pair(int first, int second) { First = first; Second = second; }}class GFG { // Function to find the minimum number // of swaps required to sort the array // in increasing order static int MinSwapsAsc(int[] arr, int n) { // Stores the array elements with // its index Pair[] arrPos = new Pair[n]; for (int i = 0; i < n; i++) { arrPos[i] = new Pair(arr[i], i); } // Sort the array in the // increasing order Array.Sort(arrPos, (a, b) => a.First - b.First); // Keeps the track of // visited elements bool[] vis = new bool[n]; // Stores the count of swaps required int ans = 0; for (int i = 0; i < n; i++) { // If the element is already // swapped or at correct position if (vis[i] || arrPos[i].Second == i) { continue; } // Find out the number of // nodes in this cycle int cycleSize = 0; // Update the value of j int j = i; while (!vis[j]) { vis[j] = true; j = arrPos[j].Second; cycleSize++; } // Update the ans by adding // current cycle if (cycleSize > 0) { ans += cycleSize - 1; } } return ans; } // Function to find the minimum number // of swaps required to sort the array // in decreasing order static int MinSwapsDes(int[] arr, int n) { // Stores the array elements with // its index Pair[] arrPos = new Pair[n]; for (int i = 0; i < n; i++) { arrPos[i] = new Pair(arr[i], i); } // Sort the array in the // descending order Array.Sort(arrPos, (a, b) => b.First - a.First); bool[] vis = new bool[n]; // Stores the count of resultant // swap required int ans = 0; // Traverse array elements for (int i = 0; i < n; i++) { // If the element is already // swapped or at correct // position if (vis[i] || arrPos[i].Second == i) { continue; } // Find out the number of // node in this cycle int cycleSize = 0; int j = i; while (!vis[j]) { vis[j] = true; j = arrPos[j].Second; // Increment the cycle_size cycleSize++; } // Update the ans by adding // current cycle size if (cycleSize > 0) { ans += cycleSize - 1; } } return ans; } // Function to find minimum number of // swaps required to minimize the sum // of absolute difference of adjacent // elements static int MinimumSwaps(int[] arr) { // Sort in ascending order int S1 = MinSwapsAsc(arr, arr.Length); // Sort in descending order int S2 = MinSwapsDes(arr, arr.Length); // Return the minimum value return Math.Min(S1, S2); } // Driver code static void Main(string[] args) { int[] arr = { 3, 4, 2, 5, 1 }; Console.WriteLine(MinimumSwaps(arr)); }}// This code is contributed by phasing17 |
Javascript
<script> // Javascript program for the above approach // Comparator to sort in the descending // order function mycmp(a, b) { return a[0] > b[0]; } // Function to find the minimum number // of swaps required to sort the array // in increasing order function minSwapsAsc(arr, n) { // Stores the array elements with // its index let arrPos = new Array(n); for (let i = 0; i < n; i++) arrPos[i] = new Array(2); for (let i = 0; i < n; i++) { arrPos[i][0] = arr[i]; arrPos[i][1] = i; } // Sort the array in the // increasing order arrPos.sort(function (a, b) { return a[0] - b[0] }) // Keeps the track of // visited elements let vis = new Array(n); for (let i = 0; i < n; i++) vis[i] = false // Stores the count of swaps required let ans = 0; // Traverse array elements for (let i = 0; i < n; i++) { // If the element is already // swapped or at correct position if (vis[i] || arrPos[i][1] == i) continue; // Find out the number of // nodes in this cycle let cycle_size = 0; // Update the value of j let j = i; while (!vis[j]) { vis[j] = 1; // Move to the next element j = arrPos[j][1]; // Increment cycle_size cycle_size++; } // Update the ans by adding // current cycle if (cycle_size > 0) { ans += (cycle_size - 1); } } return ans; } // Function to find the minimum number // of swaps required to sort the array // in decreasing order function minSwapsDes(arr, n) { // Stores the array elements with // its index let arrPos = new Array(n); for (let i = 0; i < n; i++) arrPos[i] = new Array(2); for (let i = 0; i < n; i++) { arrPos[i][0] = arr[i]; arrPos[i][1] = i; } // Sort the array in the // descending order arrPos.sort(function (a, b) { return b[0] - a[0] }) // Keeps track of visited elements let vis = new Array(n); for (let i = 0; i < n; i++) vis[i] = false // Stores the count of resultant // swap required let ans = 0; // Traverse array elements for (let i = 0; i < n; i++) { // If the element is already // swapped or at correct // position if (vis[i] || arrPos[i][1] == i) continue; // Find out the number of // node in this cycle let cycle_size = 0; // Update the value of j let j = i; while (!vis[j]) { vis[j] = 1; // Move to the next element j = arrPos[j][1]; // Increment the cycle_size cycle_size++; } // Update the ans by adding // current cycle size if (cycle_size > 0) { ans += (cycle_size - 1); } } return ans; } // Function to find minimum number of // swaps required to minimize the sum // of absolute difference of adjacent // elements function minimumSwaps(arr) { // Sort in ascending order let S1 = minSwapsAsc(arr, arr.length); // Sort in descending order let S2 = minSwapsDes(arr, arr.length); // Return the minimum value return Math.min(S1, S2); } // Drive Code let arr = [ 3, 4, 2, 5, 1 ]; document.write(minimumSwaps(arr)); // This code is contributed by Hritik </script> |
Output:
2
Time Complexity: O(N * log N), The time complexity of this code is O(Nl*ogN), where N is the size of the array. The reason behind this time complexity is due to the sorting algorithm used to sort the array. The code uses the built-in sort() function to sort the array elements in both ascending and descending order. The time complexity of the sort() function is O(N*logN), which dominates the overall time complexity of the code.
Auxiliary Space: O(N), The space complexity of this code is O(N). The reason behind this space complexity is due to the usage of two additional data structures – vector<bool> vis(n, false) and pair<int, int> arrPos[n]. The vis vector is used to keep track of visited elements during the traversal of the array, and arrPos is used to store the index and value of each element in the array. Both of these data structures have a space complexity of O(N). Therefore, the overall space complexity of the code is O(N).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
