Given an array arr[] consisting of N integers, the task is to find the lexicographically largest permutation of the given array possible by exactly one swap, which is smaller than the given array. If it is possible to obtain such a permutation, then print that permutation. Otherwise, print “-1”.
Examples:
Input: arr[] = {5, 4, 3, 2, 1}
Output: 5 4 3 1 2
Explanation:
Lexicographically, the largest permutation which is smaller than the given array can be formed by swapping 2 and 1.
Hence, the resultant permutation is {5, 4, 3, 1, 2}Input: arr[] = {1, 2, 3, 4, 5}
Output: -1
Approach: The given problem can be solved by finding the last element which is greater than its next element, and swapping it with the next smaller element in the array. Follow the steps below to solve the problem:
- If the given array is sorted in ascending order, then print “-1” as it is not possible to find lexicographically the largest permutation of the given array which is smaller than the given array.
- Traverse the given array from the end and find that index, say idx which is strictly greater than the next element.
- Now, again traverse the given array from the end and find the index(say j) of the first element, which is smaller, the element arr[idx].
- Decreasing the value of j until arr[j – 1] is the same as arr[j].
- Swap the elements at the index idx and j in the array arr[] to get the resultant permutation.
- After completing the above steps, print the array as the resultant permutation.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to lexicographic largest// permutation possible by a swap// that is smaller than given arrayvoid findPermutation(vector<int>& arr){ int N = arr.size(); int i = N - 2; // Find the index of first element // such that arr[i] > arr[i + 1] while (i >= 0 && arr[i] <= arr[i + 1]) i--; // If the array is sorted // in increasing order if (i == -1) { cout << "-1"; return; } int j = N - 1; // Find the index of first element // which is smaller than arr[i] while (j > i && arr[j] >= arr[i]) j--; // If arr[j] == arr[j-1] while (j > i && arr[j] == arr[j - 1]) { // Decrement j j--; } // Swap the element swap(arr[i], arr[j]); // Print the array arr[] for (auto& it : arr) { cout << it << ' '; }}// Driver Codeint main(){ vector<int> arr = { 1, 2, 5, 3, 4, 6 }; findPermutation(arr); return 0;} |
Java
// java program for the above approachimport java.util.*;class GFG{ // Function to lexicographic largest// permutation possible by a swap// that is smaller than given arraystatic void findPermutation(int[] arr){ int N = arr.length; int i = N - 2; // Find the index of first element // such that arr[i] > arr[i + 1] while (i >= 0 && arr[i] <= arr[i + 1]) i--; // If the array is sorted // in increasing order if (i == -1) { System.out.print("-1"); return; } int j = N - 1; // Find the index of first element // which is smaller than arr[i] while (j > i && arr[j] >= arr[i]) j--; // If arr[j] == arr[j-1] while (j > i && arr[j] == arr[j - 1]) { // Decrement j j--; } // Swap the element int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; // Print the array arr[] for(int it : arr) { System.out.print(it + " "); }}// Driver codepublic static void main(String[] args){ int[] arr = { 1, 2, 5, 3, 4, 6 }; findPermutation(arr);}}// This code is contributed by splevel62. |
C#
// C# program for the above approachusing System;class GFG{// Function to lexicographic largest// permutation possible by a swap// that is smaller than given arraystatic void findPermutation(int[] arr){ int N = arr.Length; int i = N - 2; // Find the index of first element // such that arr[i] > arr[i + 1] while (i >= 0 && arr[i] <= arr[i + 1]) i--; // If the array is sorted // in increasing order if (i == -1) { Console.Write("-1"); return; } int j = N - 1; // Find the index of first element // which is smaller than arr[i] while (j > i && arr[j] >= arr[i]) j--; // If arr[j] == arr[j-1] while (j > i && arr[j] == arr[j - 1]) { // Decrement j j--; } // Swap the element int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; // Print the array arr[] foreach(int it in arr) { Console.Write(it + " "); }}// Driver Codepublic static void Main(){ int[] arr = { 1, 2, 5, 3, 4, 6 }; findPermutation(arr);}}// This code is contributed by ukasp |
Python3
# Python program for the above approach# Function to lexicographic largest# permutation possible by a swap# that is smaller than given arraydef findPermutation(arr): N = len(arr) i = N - 2 # Find the index of first element # such that arr[i] > arr[i + 1] while (i >= 0 and arr[i] <= arr[i + 1]): i -= 1 # If the array is sorted # in increasing order if (i == -1) : print("-1") return j = N - 1 # Find the index of first element # which is smaller than arr[i] while (j > i and arr[j] >= arr[i]): j -= 1 # If arr[j] == arr[j-1] while (j > i and arr[j] == arr[j - 1]) : # Decrement j j -= 1 # Swap the element temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; # Pr the array arr[] for it in arr : print(it, end = " ") # Driver Codearr = [ 1, 2, 5, 3, 4, 6 ] findPermutation(arr)# This code is contributed by code_hunt. |
Javascript
<script>// Javascript program for the above approach// Function to lexicographic largest// permutation possible by a swap// that is smaller than given arrayfunction findPermutation(arr){ let N = arr.length; let i = N - 2; // Find the index of first element // such that arr[i] > arr[i + 1] while (i >= 0 && arr[i] <= arr[i + 1]) i--; // If the array is sorted // in increasing order if (i == -1) { document.write("-1"); return; } let j = N - 1; // Find the index of first element // which is smaller than arr[i] while (j > i && arr[j] >= arr[i]) j--; // If arr[j] == arr[j-1] while (j > i && arr[j] == arr[j - 1]) { // Decrement j j--; } // Swap the element let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; // Print the array arr[] for(let it in arr) { document.write(arr[it] + " "); }}// Driver Code let arr = [ 1, 2, 5, 3, 4, 6 ]; findPermutation(arr); </script> |
Output:
1 2 4 3 5 6
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!
