Given an array arr[] of size N, the task is to find the minimum count of adjacent swaps required to rearrange the array elements such that the largest and the smallest array element present on the first and the last indices of the array respectively.
Examples:
Input: arr[] = {33, 44, 11, 12}
Output: 2
Explanation:
Swapping the pair (arr[0], arr[1]) modifies arr[] to {44, 33, 11, 12}
Swapping the pair (arr[2], arr[3]) modifies arr[] to {44, 33, 12, 11}
Therefore, the required output is 2.
Input: arr[]={11, 12, 58, 1, 78, 40, 76}
Output: 6
Approach: Follow the steps below to solve the problem:
- Traverse the array and calculate the index of the first occurrence of the largest array element say, X, and the last occurrence of the smallest array element say, Y.
- The count of adjacent swaps required to move the largest array element at the first index is equal to X.
- The count of adjacent swaps required to move the smallest array element at the last index is equal to N – 1 – Y.
- If X > Y, then one adjacent swap common in moving the largest element at the first index and the smallest element at the last index. Therefore, the total count of adjacent swaps required is equal to X + (N – 1 – Y) – 1.
- Otherwise, the total count of adjacent swaps required is equal to X + (N – 1 – Y).
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum count of adjacent// swaps to move largest and smallest element at the// first and the last index of the array, respectivelyint minimumMoves(int* a, int n){ // Stores the smallest array element int min_element = INT_MAX; // Stores the smallest array element int max_element = INT_MIN; // Stores the last occurrence of // the smallest array element int min_ind = -1; // Stores the first occurrence of // the largest array element int max_ind = -1; // Traverse the array a[] for (int i = 0; i < n; i++) { // If a[i] is less than // min_element if (a[i] <= min_element) { // Update min_element min_element = a[i]; // Update min_ind min_ind = i; } // If a[i] is greater than // max_element if (a[i] > max_element) { // Update max_element max_element = a[i]; // Update max_ind max_ind = i; } } // If max_ind is equal // to min_ind if (max_ind == min_ind) { // Return 0 return 0; } // If max_ind is greater than min_ind else if (max_ind > min_ind) { return max_ind + (n - min_ind - 2); } // Otherwise else { return max_ind + n - min_ind - 1; }}// Driver Codeint main(){ // Input int arr[] = { 35, 46, 17, 23 }; int N = sizeof(arr) / sizeof(arr[0]); // Print the result cout << minimumMoves(arr, N) << endl;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the minimum count of adjacent// swaps to move largest and smallest element at the// first and the last index of the array, respectivelystatic int minimumMoves(int []a, int n){ // Stores the smallest array element int min_element = Integer.MAX_VALUE; // Stores the smallest array element int max_element = Integer.MIN_VALUE; // Stores the last occurrence of // the smallest array element int min_ind = -1; // Stores the first occurrence of // the largest array element int max_ind = -1; // Traverse the array arr[] for (int i = 0; i < n; i++) { // If a[i] is less than // min_element if (a[i] <= min_element) { // Update min_element min_element = a[i]; // Update min_ind min_ind = i; } // If a[i] is greater than // max_element if (a[i] > max_element) { // Update max_element max_element = a[i]; // Update max_ind max_ind = i; } } // If max_ind is equal // to min_ind if (max_ind == min_ind) { // Return 0 return 0; } // If max_ind is greater than min_ind else if (max_ind > min_ind) { return max_ind + (n - min_ind - 2); } // Otherwise else { return max_ind + n - min_ind - 1; }}// Driver Codepublic static void main(String[] args){ // Input int arr[] = { 35, 46, 17, 23 }; int N = arr.length; // Print the result System.out.print(minimumMoves(arr, N) +"\n");}}// This code is contributed by 29AjayKumar |
Python3
# Python 3 program for the above approachimport sys# Function to find the minimum count of adjacent# swaps to move largest and smallest element at the# first and the last index of the array, respectivelydef minimumMoves(a, n): # Stores the smallest array element min_element = sys.maxsize # Stores the smallest array element max_element = -sys.maxsize - 1 # Stores the last occurrence of # the smallest array element min_ind = -1 # Stores the first occurrence of # the largest array element max_ind = -1 # Traverse the array arr[] for i in range(n): # If a[i] is less than # min_element if (a[i] <= min_element): # Update min_element min_element = a[i] # Update min_ind min_ind = i # If a[i] is greater than # max_element if (a[i] > max_element): # Update max_element max_element = a[i] # Update max_ind max_ind = i # If max_ind is equal # to min_ind if (max_ind == min_ind): # Return 0 return 0 # If max_ind is greater than min_ind elif(max_ind > min_ind): return max_ind + (n - min_ind - 2) # Otherwise else: return max_ind + n - min_ind - 1# Driver Codeif __name__ == '__main__': # Input arr = [35, 46, 17, 23] N = len(arr) # Print the result print(minimumMoves(arr, N)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;public class GFG{ // Function to find the minimum count of adjacent // swaps to move largest and smallest element at the // first and the last index of the array, respectively static int minimumMoves(int []a, int n) { // Stores the smallest array element int min_element = int.MaxValue; // Stores the smallest array element int max_element = int.MinValue; // Stores the last occurrence of // the smallest array element int min_ind = -1; // Stores the first occurrence of // the largest array element int max_ind = -1; // Traverse the array []arr for (int i = 0; i < n; i++) { // If a[i] is less than // min_element if (a[i] <= min_element) { // Update min_element min_element = a[i]; // Update min_ind min_ind = i; } // If a[i] is greater than // max_element if (a[i] > max_element) { // Update max_element max_element = a[i]; // Update max_ind max_ind = i; } } // If max_ind is equal // to min_ind if (max_ind == min_ind) { // Return 0 return 0; } // If max_ind is greater than min_ind else if (max_ind > min_ind) { return max_ind + (n - min_ind - 2); } // Otherwise else { return max_ind + n - min_ind - 1; } } // Driver Code public static void Main(String[] args) { // Input int []arr = { 35, 46, 17, 23 }; int N = arr.Length; // Print the result Console.Write(minimumMoves(arr, N) +"\n"); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program of the above approach// Function to find the minimum count of adjacent// swaps to move largest and smallest element at the// first and the last index of the array, respectivelyfunction minimumMoves(a, n){ // Stores the smallest array element let min_element = Number.MAX_VALUE; // Stores the smallest array element let max_element = Number.MIN_VALUE; // Stores the last occurrence of // the smallest array element let min_ind = -1; // Stores the first occurrence of // the largest array element let max_ind = -1; // Traverse the array arr[] for (let i = 0; i < n; i++) { // If a[i] is less than // min_element if (a[i] <= min_element) { // Update min_element min_element = a[i]; // Update min_ind min_ind = i; } // If a[i] is greater than // max_element if (a[i] > max_element) { // Update max_element max_element = a[i]; // Update max_ind max_ind = i; } } // If max_ind is equal // to min_ind if (max_ind == min_ind) { // Return 0 return 0; } // If max_ind is greater than min_ind else if (max_ind > min_ind) { return max_ind + (n - min_ind - 2); } // Otherwise else { return max_ind + n - min_ind - 1; }} // Driver Code // Input let arr = [ 35, 46, 17, 23 ]; let N = arr.length; // Print the result document.write(minimumMoves(arr, N) +"\n");</script> |
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
