Given an array arr[] of N integers, the task is to find the lexicographically largest permutation by sequentially inserting the array elements to the front or the back of another array.
Examples:
Input: arr[] = {3, 1, 2, 4}
Output: 4 3 1 2
Explanation:
The permutations that can be created by sequentially inserting the array elements to the front or the back of the container are {3, 1, 2, 4}, {1, 3, 2, 4}, {2, 3, 1, 4}, {2, 1, 3, 4}, {4, 1, 3, 2}, {4, 2, 3, 1}, {4, 2, 1, 3}, and {4, 3, 1, 2}. Out of which {4, 3, 1, 2} is the lexicographically largest permutation.Input: arr[] = {1, 2, 3, 4, 5}
Output: 5 4 3 2 1
Approach: The given problem can be solved by using the Greedy Approach using the deque which is based on the observation that if the current array element is at least the first element of the new array, the most optimal choice always is to insert that element in front of the container in order to lexicographically maximize the permutation. Otherwise, insert the element to the end of the array. Follow the steps below to solve the given problem:
- Initialize a deque, say DQ, which stores the current state of the container.
- Initialize a variable, say mx, which stores the maximum till each index representing the 1st element of the deque DQ.
- Traverse the given array arr[] and if the current element arr[i] >= mx, then insert arr[i] to the front of the deque DQ and update the value of mx. Otherwise, insert arr[i] to the back of the deque DQ.
- After completing the above steps, print the elements stored in the deque DQ as the resultant largest 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 find the lexicographically// largest permutation by sequentially// inserting the array elementsvoid largestPermutation(int arr[], int N){ // Stores the current state of // the new array deque<int> p; // Stores the current maximum // element of array arr[] int mx = arr[0]; p.push_back(arr[0]); // Iterate the array elements for (int i = 1; i < N; i++) { // If the current element is // smaller than the current // maximum, then insert if (arr[i] < mx) p.push_back(arr[i]); // If the current element is // at least the current maximum else { p.push_front(arr[i]); // Update the value of // the current maximum mx = arr[i]; } } // Print resultant permutation for (auto i : p) cout << i << " ";}// Driver Codeint main(){ int arr[] = { 3, 1, 2, 4 }; int N = sizeof(arr) / sizeof(arr[0]); largestPermutation(arr, N); return 0;} |
Java
// Java code for the above approachimport java.util.*;class GFG { // Function to find the lexicographically // largest permutation by sequentially // inserting the array elements static void largestPermutation(int arr[], int N) { // Stores the current state of // the new array Deque<Integer> p = new LinkedList<Integer>(); // Stores the current maximum // element of array arr[] int mx = arr[0]; p.addLast(arr[0]); // Iterate the array elements for (int i = 1; i < N; i++) { // If the current element is // smaller than the current // maximum, then insert if (arr[i] < mx) p.addLast(arr[i]); // If the current element is // at least the current maximum else { p.addFirst(arr[i]); // Update the value of // the current maximum mx = arr[i]; } } // Print resultant permutation for (Iterator itr = p.iterator(); itr.hasNext();) { System.out.print(itr.next() + " "); } } // Driver Code public static void main(String[] args) { int arr[] = { 3, 1, 2, 4 }; int N = arr.length; largestPermutation(arr, N); }}// This code is contributed by Potta Lokesh |
Python3
# python program for the above approach# Function to find the lexicographically# largest permutation by sequentially# inserting the array elementsfrom typing import Dequedef largestPermutation(arr, N): # Stores the current state of # the new array p = Deque() # Stores the current maximum # element of array arr[] mx = arr[0] p.append(arr[0]) # Iterate the array elements for i in range(1, N): # If the current element is # smaller than the current # maximum, then insert if (arr[i] < mx): p.append(arr[i]) # If the current element is # at least the current maximum else: p.appendleft(arr[i]) # Update the value of # the current maximum mx = arr[i] # Print resultant permutation for i in p: print(i, end=" ")# Driver Codeif __name__ == "__main__": arr = [3, 1, 2, 4] N = len(arr) largestPermutation(arr, N)# This code is contributed by rakeshsahni |
C#
// C# code for the above approachusing System;using System.Linq;using System.Collections.Generic;public class GFG { // Function to find the lexicographically // largest permutation by sequentially // inserting the array elements static void largestPermutation(int []arr, int N) { // Stores the current state of // the new array List<int> p = new List<int>(); // Stores the current maximum // element of array []arr int mx = arr[0]; p.Add(arr[0]); // Iterate the array elements for (int i = 1; i < N; i++) { // If the current element is // smaller than the current // maximum, then insert if (arr[i] < mx) p.Add(arr[i]); // If the current element is // at least the current maximum else { p.Insert(0,arr[i]); // Update the value of // the current maximum mx = arr[i]; } } // Print resultant permutation foreach (int itr in p) { Console.Write(itr + " "); } } // Driver Code public static void Main(String[] args) { int []arr = { 3, 1, 2, 4 }; int N = arr.Length; largestPermutation(arr, N); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program for the above approach// Function to find the lexicographically// largest permutation by sequentially// inserting the array elementsfunction largestPermutation(arr, N){ // Stores the current state of // the new array let p = []; // Stores the current maximum // element of array arr[] let mx = arr[0]; p.push(arr[0]); // Iterate the array elements for (let i = 1; i < N; i++) { // If the current element is // smaller than the current // maximum, then insert if (arr[i] < mx) p.push(arr[i]); // If the current element is // at least the current maximum else { p.unshift(arr[i]); // Update the value of // the current maximum mx = arr[i]; } } // Print resultant permutation for (i of p) document.write(i + " ");}// Driver Codelet arr = [3, 1, 2, 4];let N = arr.length;largestPermutation(arr, N);// This code is contributed by gfgking.</script> |
Output:
4 3 1 2
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
