Given an array arr[] consisting of N integers, the task is to find the minimum number of adjacent swaps required to make the first and the last elements in the array the largest and smallest element present in the array respectively.
Examples:
Input: arr[] = {1, 3, 2}
Output: 2
Explanation:
Initially the array is {1, 3, 2}.
Operation 1: Swap element at index 0 and 1. The array modifies to {3, 1, 2}.
Operation 2: Swap element at index 1 and 2. The array modifies to {3, 2, 1}.
Therefore, the minimum number of operation required is 2.Input: arr[] = {100, 95, 100, 100, 88}
Output: 0
Approach: Follow the steps below to solve the given problem:
- Initialize a variable, say, count, to store the total number of swaps required.
- Find the minimum and the maximum element of the array and store it in a variable, say minElement and maxElement respectively.
- If the minimum and maximum elements are found to be the same, the array consists of a single distinct element. Therefore, print 0 as both the elements are at their correct positions respectively.
- Otherwise, traverse the array and find the index of the first occurrence of maxElement and the last occurrence of minElement and store it in a variable, say minIndex and maxIndex respectively.
- Update the value of count as the sum of maxIndex and (N – 1 – minIndex) as the number of swap operations required to make the largest and the smallest element as the first and the last elements of the array respectively.
- If minIndex is less than maxIndex, then decrease count by 1, as one swap operation will overlap.
- After completing the above steps, print the value of count as the 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;// Function to find the minimum number// of swaps required to make the first// and the last elements the largest// and smallest element in the arrayint minimum_swaps(int arr[], int n){ // Stores the count of swaps int count = 0; // Stores the maximum element int max_el = *max_element(arr, arr + n); // Stores the minimum element int min_el = *min_element(arr, arr + n); // If the array contains // a single distinct element if (min_el == max_el) return 0; // Stores the indices of the // maximum and minimum elements int index_max = -1; int index_min = -1; for (int i = 0; i < n; i++) { // If the first index of the // maximum element is found if (arr[i] == max_el && index_max == -1) { index_max = i; } // If current index has // the minimum element if (arr[i] == min_el) { index_min = i; } } // Update the count of operations to // place largest element at the first count += index_max; // Update the count of operations to // place largest element at the last count += (n - 1 - index_min); // If smallest element is present // before the largest element initially if (index_min < index_max) count -= 1; return count;}// Driver Codeint main(){ int arr[] = { 2, 4, 1, 6, 5 }; int N = sizeof(arr) / sizeof(arr[0]); cout << minimum_swaps(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.Arrays;import java.util.Collections;class GFG{// Function to find the minimum number// of swaps required to make the first// and the last elements the largest// and smallest element in the arraystatic int minimum_swaps(Integer arr[], int n){ // Stores the count of swaps int count = 0; // Stores the maximum element int max_el = Collections.max(Arrays.asList(arr)); // Stores the minimum element int min_el = Collections.min(Arrays.asList(arr)); // If the array contains // a single distinct element if (min_el == max_el) return 0; // Stores the indices of the // maximum and minimum elements int index_max = -1; int index_min = -1; for(int i = 0; i < n; i++) { // If the first index of the // maximum element is found if (arr[i] == max_el && index_max == -1) { index_max = i; } // If current index has // the minimum element if (arr[i] == min_el) { index_min = i; } } // Update the count of operations to // place largest element at the first count += index_max; // Update the count of operations to // place largest element at the last count += (n - 1 - index_min); // If smallest element is present // before the largest element initially if (index_min < index_max) count -= 1; return count;}// Driver Codepublic static void main (String[] args){ Integer arr[] = { 2, 4, 1, 6, 5 }; int N = arr.length; System.out.println(minimum_swaps(arr, N));}}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to find the minimum number# of swaps required to make the first# and the last elements the largest# and smallest element in the arraydef minimum_swaps(arr, n): # Stores the count of swaps count = 0 # Stores the maximum element max_el = max(arr) # Stores the minimum element min_el = min(arr) # If the array contains # a single distinct element if (min_el == max_el): return 0 # Stores the indices of the # maximum and minimum elements index_max = -1 index_min = -1 for i in range(n): # If the first index of the # maximum element is found if (arr[i] == max_el and index_max == -1): index_max = i # If current index has # the minimum element if (arr[i] == min_el): index_min = i # Update the count of operations to # place largest element at the first count += index_max # Update the count of operations to # place largest element at the last count += (n - 1 - index_min) # If smallest element is present # before the largest element initially if (index_min < index_max): count -= 1 return count# Driver Codeif __name__ == '__main__': arr = [2, 4, 1, 6, 5] N = len(arr) print(minimum_swaps(arr, N))# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Linq;class GFG{// Function to find the minimum number// of swaps required to make the first// and the last elements the largest// and smallest element in the arraystatic int minimum_swaps(int[] arr, int n){ // Stores the count of swaps int count = 0; // Stores the maximum element int max_el = arr.Max(); // Stores the minimum element int min_el = arr.Min(); // If the array contains // a single distinct element if (min_el == max_el) return 0; // Stores the indices of the // maximum and minimum elements int index_max = -1; int index_min = -1; for(int i = 0; i < n; i++) { // If the first index of the // maximum element is found if (arr[i] == max_el && index_max == -1) { index_max = i; } // If current index has // the minimum element if (arr[i] == min_el) { index_min = i; } } // Update the count of operations to // place largest element at the first count += index_max; // Update the count of operations to // place largest element at the last count += (n - 1 - index_min); // If smallest element is present // before the largest element initially if (index_min < index_max) count -= 1; return count;}// Driver Codepublic static void Main(string[] args){ int[] arr = { 2, 4, 1, 6, 5 }; int N = arr.Length; Console.WriteLine(minimum_swaps(arr, N));}}// This code is contributed by ukasp |
Javascript
<script> // JavaScript program for the above approach // Function to find the minimum number // of swaps required to make the first // and the last elements the largest // and smallest element in the array function minimum_swaps(arr, n) { // Stores the count of swaps var count = 0; // Stores the maximum element var max_el = Math.max(...arr); // Stores the minimum element var min_el = Math.min(...arr); // If the array contains // a single distinct element if (min_el === max_el) return 0; // Stores the indices of the // maximum and minimum elements var index_max = -1; var index_min = -1; for (var i = 0; i < n; i++) { // If the first index of the // maximum element is found if (arr[i] === max_el && index_max === -1) { index_max = i; } // If current index has // the minimum element if (arr[i] === min_el) { index_min = i; } } // Update the count of operations to // place largest element at the first count += index_max; // Update the count of operations to // place largest element at the last count += n - 1 - index_min; // If smallest element is present // before the largest element initially if (index_min < index_max) count -= 1; return count; } // Driver Code var arr = [2, 4, 1, 6, 5]; var N = arr.length; document.write(minimum_swaps(arr, N)); </script> |
Output:
4
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!
