Lexicographically largest permutation of array possible by reversing suffix subarrays
Given an array arr[] of size N, the task is to find the lexicographically largest permutation array by reversing any suffix subarrays from the array.
Examples:
Input: arr[] = {3, 5, 4, 1, 2}
Output: 3 5 4 2 1
Explanation: Reversing the suffix subarray {1, 2} generates the lexicographically largest permutation of the array elements possible.Input: arr[] = {3, 5, 1, 2, 1}
Output: 3 5 1 2 1
Explanation:
The given array arr[] is already the lexicographically largest permutation of the array possible.
Naive Approach: The simplest approach is to reverse every possible suffix subarrays from the array and print the permutation of array elements that is lexicographically largest possible.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to use Greedy Approach. The given problem can be solved based on the following observations:
It can be observed that by choosing the suffix array as subarray in the range [i, N – 1] such that arr[i] < arr[N – 1] and reversing it, the obtained array will be lexicographically the largest array.
Follow the steps below to solve the problem:
- Initialize a variable, say flag as -1, that represents an index is found which has the value less than the last element.
- Traverse the given array arr[] and in each iteration, check if arr[i] < arr[N – 1] or not. Then, store the current index in the variable flag and break the loop.
- After completing the above steps, check if the value of flag is -1 or not. If found to be true, then reverse the suffix subarray i.e., subarray in the range [flag, N – 1].
- After completing the above steps, print the array arr[] as the result.
Below is the implementation of the above approach:
C++
// CPP program for the above approach #include <bits/stdc++.h> using namespace std; // Function that void LLA(vector< int > A) { // Stores the index that have // element less than the // element at last index int flg = -1; // Traverse the array for ( int i = 0; i < A.size(); i++) { // Checks if value at the // current index is less // than value at last index if (A[i] < A[A.size() - 1]) { // Assign the current // index value to index flg = i; break ; } } // Check if index is not -1 then // reverse the suffix from the // index stored at flg if (flg != -1) { // Reversal of suffix for ( int i = flg, j = A.size() - 1; i <= j; i++, j--) { // Swapping Step int temp = A[i]; A[i] = A[j]; A[j] = temp; } } // Print the final Array for ( int i = 0; i < A.size(); i++) cout<<A[i]<< " " ; } // Driver Code int main() { vector< int > arr= { 3, 5, 4, 1, 2 }; // Function Call LLA(arr); } // This code is contributed by mohit kumar 29. |
Java
// Java program for the above approach import java.io.*; class GFG { // Function that public static void LLA( int A[]) { // Stores the index that have // element less than the // element at last index int flg = - 1 ; // Traverse the array for ( int i = 0 ; i < A.length; i++) { // Checks if value at the // current index is less // than value at last index if (A[i] < A[A.length - 1 ]) { // Assign the current // index value to index flg = i; break ; } } // Check if index is not -1 then // reverse the suffix from the // index stored at flg if (flg != - 1 ) { // Reversal of suffix for ( int i = flg, j = A.length - 1 ; i <= j; i++, j--) { // Swapping Step int temp = A[i]; A[i] = A[j]; A[j] = temp; } } // Print the final Array for ( int i = 0 ; i < A.length; i++) System.out.print(A[i] + " " ); } // Driver Code public static void main(String[] args) { int arr[] = { 3 , 5 , 4 , 1 , 2 }; // Function Call LLA(arr); } } |
Python3
# Python program for the above approach # Function that def LLA(A): # Stores the index that have # element less than the # element at last index flg = - 1 ; # Traverse the array for i in range ( len (A)): # Checks if value at the # current index is less # than value at last index if (A[i] < A[ len (A) - 1 ]): # Assign the current # index value to index flg = i; break ; # Check if index is not -1 then # reverse the suffix from the # index stored at flg if (flg ! = - 1 ): # Reversal of suffix j = len (A) - 1 ; for i in range (flg, j + 1 ): # Swapping Step temp = A[i]; A[i] = A[j]; A[j] = temp; j - = 1 ; # Print the final Array for i in range ( len (A)): print (A[i], end = " " ); # Driver Code if __name__ = = '__main__' : arr = [ 3 , 5 , 4 , 1 , 2 ]; # Function Call LLA(arr); # This code is contributed by 29AjayKumar |
C#
// C# program for the above approach using System; public class GFG { // Function that public static void LLA( int []A) { // Stores the index that have // element less than the // element at last index int flg = -1; // Traverse the array for ( int i = 0; i < A.Length; i++) { // Checks if value at the // current index is less // than value at last index if (A[i] < A[A.Length - 1]) { // Assign the current // index value to index flg = i; break ; } } // Check if index is not -1 then // reverse the suffix from the // index stored at flg if (flg != -1) { // Reversal of suffix for ( int i = flg, j = A.Length - 1; i <= j; i++, j--) { // Swapping Step int temp = A[i]; A[i] = A[j]; A[j] = temp; } } // Print the readonly Array for ( int i = 0; i < A.Length; i++) Console.Write(A[i] + " " ); } // Driver Code public static void Main(String[] args) { int []arr = { 3, 5, 4, 1, 2 }; // Function Call LLA(arr); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for the above approach // Function that function LLA(A) { // Stores the index that have // element less than the // element at last index var flg = -1; var i,j; // Traverse the array for (i = 0; i < A.length; i++) { // Checks if value at the // current index is less // than value at last index if (A[i] < A[A.length - 1]) { // Assign the current // index value to index flg = i; break ; } } // Check if index is not -1 then // reverse the suffix from the // index stored at flg if (flg != -1) { // Reversal of suffix for (i = flg, j = A.length - 1; i <= j; i++, j--) { // Swapping Step var temp = A[i]; A[i] = A[j]; A[j] = temp; } } // Print the final Array for (i = 0; i < A.length; i++) document.write(A[i] + " " ); } // Driver Code var arr = [3, 5, 4, 1, 2]; // Function Call LLA(arr); </script> |
3 5 4 2 1
Time Complexity: O(N)
Auxiliary Space: O(1)