Lexicographically smallest permutation of the array possible by at most one swap
Given an array arr[] representing a permutation of first N natural numbers, the task is to find the lexicographically smallest permutation of the given array arr[] possible by swapping at most one pair of array elements. If it is not possible to make the array lexicographically smaller, then print “-1”.
Examples:
Input: arr[] = {3, 2, 1, 4}
Output: 1 2 3 4
Explanation: Swapping elements at index 2 and 0, the modified array is {1, 2, 3, 4}, which is lexicographically the smallest permutation of the given array arr[].Input: arr[] = {1, 2, 3, 4}
Output: -1
Approach: The idea is to find the first array element which is not at its correct position i.e., arr[i] is not the same as the index (i + 1), and swap it with the element at its correct position. Follow the steps below to solve this problem:
- Traverse the array arr[] and find the index i such that arr[i] is not equal to (i + 1), say idx, and store (i + 1) in a variable, say ele.
- Now, find the index of ele, say newIdx.
- After completing the above steps, there exists two indices idx and newIdx. The lexicographically smallest permutation of the array can be formed by swapping elements at indices idx and newIdx. Now, print the array arr[]. Otherwise, print “-1”.
Below is the implementation of the above approach:
C++14
// C++ implementation of the above approach #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to print the // elements of the array arr[] void print( int arr[], int N) { // Traverse the array arr[] for ( int i = 0; i < N; i++) { cout << arr[i] << " " ; } } // Function to convert given array to // lexicographically smallest permutation // possible by swapping at most one pair void makeLexicographically( int arr[], int N) { // Stores the index of the first // element which is not at its // correct position int index = 0; int temp = 0; // Checks if any such array // element exists or not int check = 0; int condition = 0; int element = 0; // Traverse the given array for ( int i = 0; i < N; ++i) { // If element is found at i if (element == arr[i]) { check = i; break ; } // If the first array is // not in correct position else if (arr[i] != i + 1 && check == 0) { // Store the index of // the first elements index = i; check = 1; condition = -1; // Store the index of // the first element element = i + 1; } } // Swap the pairs if (condition == -1) { temp = arr[index]; arr[index] = arr[check]; arr[check] = temp; } // Print the array print(arr, N); } // Driver code int main() { // Given array int arr[] = { 1, 2, 3, 4 }; // Store the size of the array int N = sizeof (arr) / sizeof (arr[0]); makeLexicographically(arr, N); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to print the // elements of the array arr[] static void print( int arr[]) { // Traverse the array arr[] for ( int element : arr) { System.out.print(element + " " ); } } // Function to convert given array to // lexicographically smallest permutation // possible by swapping at most one pair static void makeLexicographically( int arr[], int length) { // Stores the index of the first // element which is not at its // correct position int index = 0 ; int temp = 0 ; // Checks if any such array // element exists or not int check = 0 ; int condition = 0 ; int element = 0 ; // Traverse the given array for ( int i = 0 ; i < length; ++i) { // If element is found at i if (element == arr[i]) { check = i; break ; } // If the first array is // not in correct position else if (arr[i] != i + 1 && check == 0 ) { // Store the index of // the first elements index = i; check = 1 ; condition = - 1 ; // Store the index of // the first element element = i + 1 ; } } // Swap the pairs if (condition == - 1 ) { temp = arr[index]; arr[index] = arr[check]; arr[check] = temp; } // Print the array print(arr); } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 }; int N = arr.length; makeLexicographically(arr, N); } } |
Python3
# Python3 program for the above approach # Function to print the # elements of the array arr[] def printt(arr, N) : # Traverse the array arr[] for i in range (N): print (arr[i], end = " " ) # Function to convert given array to # lexicographically smallest permutation # possible by swapping at most one pair def makeLexicographically(arr, N) : # Stores the index of the first # element which is not at its # correct position index = 0 temp = 0 # Checks if any such array # element exists or not check = 0 condition = 0 element = 0 # Traverse the given array for i in range (N): # If element is found at i if (element = = arr[i]) : check = i break # If the first array is # not in correct position elif (arr[i] ! = i + 1 and check = = 0 ) : # Store the index of # the first elements index = i check = 1 condition = - 1 # Store the index of # the first element element = i + 1 # Swap the pairs if (condition = = - 1 ) : temp = arr[index] arr[index] = arr[check] arr[check] = temp # Print the array printt(arr, N) # Driver code # Given array arr = [ 1 , 2 , 3 , 4 ] # Store the size of the array N = len (arr) makeLexicographically(arr, N) # This code is contributed by code_hunt. |
C#
// C# program for the above approach using System; class GFG { // Function to print the // elements of the array arr[] static void print( int [] arr) { // Traverse the array arr[] foreach ( int element in arr) { Console.Write(element + " " ); } } // Function to convert given array to // lexicographically smallest permutation // possible by swapping at most one pair static void makeLexicographically( int []arr, int length) { // Stores the index of the first // element which is not at its // correct position int index = 0; int temp = 0; // Checks if any such array // element exists or not int check = 0; int condition = 0; int element = 0; // Traverse the given array for ( int i = 0; i < length; ++i) { // If element is found at i if (element == arr[i]) { check = i; break ; } // If the first array is // not in correct position else if (arr[i] != i + 1 && check == 0) { // Store the index of // the first elements index = i; check = 1; condition = -1; // Store the index of // the first element element = i + 1; } } // Swap the pairs if (condition == -1) { temp = arr[index]; arr[index] = arr[check]; arr[check] = temp; } // Print the array print(arr); } // Driver Code public static void Main( string [] args) { int [] arr = { 1, 2, 3, 4 }; int N = arr.Length; makeLexicographically(arr, N); } } // This code is contributed by ukasp. |
Javascript
<script> // Javascript implementation of the above approach // Function to print the // elements of the array arr[] function print(arr, N) { // Traverse the array arr[] for (i = 0; i < N; i++) { document.write(arr[i]+ " " ); } } // Function to convert given array to // lexicographically smallest permutation // possible by swapping at most one pair function makeLexicographically(arr, N) { // Stores the index of the first // element which is not at its // correct position var index = 0; var temp = 0; // Checks if any such array // element exists or not var check = 0; var condition = 0; var element = 0; // Traverse the given array for (i = 0; i < N; ++i) { // If element is found at i if (element == arr[i]) { check = i; break ; } // If the first array is // not in correct position else if (arr[i] != i + 1 && check == 0) { // Store the index of // the first elements index = i; check = 1; condition = -1; // Store the index of // the first element element = i + 1; } } // Swap the pairs if (condition == -1) { temp = arr[index]; arr[index] = arr[check]; arr[check] = temp; } // Print the array print(arr, N); } // Driver code // Given array var arr = [1, 2, 3, 4] // Store the size of the array var N = arr.length; makeLexicographically(arr, N); // This code is contributed by SURENDRA_GANGWAR. </script> |
1 2 3 4
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us