Lexicographically largest permutation by sequentially inserting Array elements at ends

Given an array arr[] of size n, the task is to find the lexicographically largest permutation by sequentially inserting the array elements to the front or the back of another array which is to be considered initially empty.

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. The idea is to simply insert the first element into an empty deque, then for the remaining elements, always put the larger element to the front and smaller element to the rear.

Step by step approach:

1. Initialize a double-ended queue with the first element arr[0].
2. Iterate through remaining elements in the original array
   • If current element ≥ front of deque, push it to front.
   • Otherwise, push it to back of deque.
3. Convert deque to array and return.

// C++ code to find Lexicographically largest permutation  // by sequentially inserting Array elements at ends #include <bits/stdc++.h> using namespace std; vector<int> largestPermutation(vector<int> &arr) {  int n = arr.size();    deque<int> dq;  dq.push_back(arr[0]);    for (int i = 1; i < n; i++) {  if (arr[i] >= dq.front()) {  dq.push_front(arr[i]);  }   else {  dq.push_back(arr[i]);  }  }    vector<int> res(dq.begin(), dq.end());  return res; } int main() {  vector<int> arr = {3, 1, 2, 4};  vector<int> res = largestPermutation(arr);  for (int num : res) {  cout << num << " ";  }  cout << endl;  return 0; } 

// Java code to find Lexicographically largest permutation  // by sequentially inserting Array elements at ends import java.util.ArrayDeque; import java.util.Deque; class GfG {  static int[] largestPermutation(int[] arr) {  int n = arr.length;    Deque<Integer> dq = new ArrayDeque<>();  dq.addLast(arr[0]);    for (int i = 1; i < n; i++) {  if (arr[i] >= dq.peekFirst()) {  dq.addFirst(arr[i]);  }   else {  dq.addLast(arr[i]);  }  }    int[] res = new int[n];  int index = 0;  for (int num : dq) {  res[index++] = num;  }  return res;  }  public static void main(String[] args) {  int[] arr = {3, 1, 2, 4};  int[] res = largestPermutation(arr);  for (int num : res) {  System.out.print(num + " ");  }  System.out.println();  } } 

# Python code to find Lexicographically largest permutation  # by sequentially inserting Array elements at ends from collections import deque def largestPermutation(arr): n = len(arr) dq = deque() dq.append(arr[0]) for i in range(1, n): if arr[i] >= dq[0]: dq.appendleft(arr[i]) else: dq.append(arr[i]) return list(dq) if __name__ == "__main__": arr = [3, 1, 2, 4] res = largestPermutation(arr) for num in res: print(num, end=" ") print() 

// C# code to find Lexicographically largest permutation  // by sequentially inserting Array elements at ends using System; using System.Collections.Generic; class GfG {    static int[] largestPermutation(int[] arr) {  int n = arr.Length;    LinkedList<int> dq = new LinkedList<int>();  dq.AddLast(arr[0]);    for (int i = 1; i < n; i++) {  if (arr[i] >= dq.First.Value) {  dq.AddFirst(arr[i]);  }  else {  dq.AddLast(arr[i]);  }  }    int[] res = new int[dq.Count];  int index = 0;  foreach (int num in dq) {  res[index++] = num;  }  return res;  }  static void Main() {  int[] arr = { 3, 1, 2, 4 };  int[] res = largestPermutation(arr);  foreach (int num in res) {  Console.Write(num + " ");  }  Console.WriteLine();  } } 

// JavaScript code to find Lexicographically largest permutation  // by sequentially inserting Array elements at ends function largestPermutation(arr) {  const n = arr.length;    const dq = [];  dq.push(arr[0]);    for (let i = 1; i < n; i++) {  if (arr[i] >= dq[0]) {  dq.unshift(arr[i]);  }   else {  dq.push(arr[i]);  }  }    return dq; } const arr = [3, 1, 2, 4]; const res = largestPermutation(arr); for (const num of res) {  process.stdout.write(num + " "); } console.log(); 

4 3 1 2 

Time Complexity: O(n)
Auxiliary Space: O(n)