Horje
Lexicographical smallest and largest Permutation from Array whose elements are max of Prefix

Given an array A[] of size N where each element A[i] =max(P[0], P[1], . . ., P[i]), where P[] is a permutation consisting of elements from 1 to N, the task is to find the lexicographically smallest and lexicographically largest permutation that satisfies A[].

Examples:

Input: A[] = {3, 4, 5, 5, 5, 7, 7}
Output: Lexicographically smallest permutation is: {3 4 5 1 2 7 6}. 
Lexicographically largest permutation is: { 3 4 5 2 1 7 6} 

Input: A[] = {2, 4, 4, 4, 6, 6}
Output: Lexicographically smallest permutation is: 2 4 1 3 6 5 
Lexicographically largest permutation is: 2 4 3 1 6 5 

Approach: This problem can be solved using this idea:

Use a set to store the first N natural number and for each element of A, find the lexicographical element satisfying A using property of set that it stores values in sorted order.

To make a permutation array, push all the natural numbers from 1 to N into a set because every element is required only once.

  • For minimum permutation, initialize the curr_max variable to 0 and traverse the array:
    • If the curr_max is less than A[i] choose the A[i]  and put it into the permutation and remove A[i] from set updating curr_max = A[i].
    • Otherwise, from the set, put the first number from the set into the position to make permutation lexicographically minimum and remove the first element of the set.
  • Second, For maximal permutation, again initialize the curr_max variable to 0 and traverse the array:
    • If the curr_max is less than A[i] choose the A[i]  and put it into the permutation and remove A[i] from set updating curr_max = A[i].
    • Otherwise, check the lower bound of A[i] and decrement the iterator to get the largest number smaller than A[i] in the set, and remove it from the set.
  • Let’s say the minimum permutation obtained is called mini and the maximum permutation obtained maxi and return that

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the max array of
// minimum and maximum permutation
// satisfying A
void findMinMaxPermutation(vector<int>& A)
{
    int n = A.size();
    set<int> s;
    vector<int> mini;
    vector<int> maxi;
 
    // Pushing all the elements into set till n
    for (int i = 1; i < n + 1; i++)
        s.insert(i);
    int curr_max = 0;
    for (int i = 0; i < n; i++) {
        int number;
 
        // If curr_max is less
        if (curr_max < A[i]) {
            number = A[i];
        }
 
        // Choosing the smallest element less than A[i]
        else
            number = *s.begin();
 
        // Erasing from set
        s.erase(number);
 
        // Pushing the elements to vector
        mini.push_back(number);
 
        // Keep updating the max
        curr_max = max(curr_max, mini.back());
    }
    curr_max = 0;
 
    // Pushing all the elements into set till n
    for (int i = 1; i < n + 1; i++)
        s.insert(i);
    for (int i = 0; i < n; i++) {
        int number;
 
        // If curr_max is less
        if (curr_max < A[i])
            number = A[i];
 
        // Choosing the bigger element but less than A[i]
        else
            number = *(--(s.lower_bound(A[i])));
 
        // Erasing from set
        s.erase(number);
 
        // Pushing the elements to vector
        maxi.push_back(number);
 
        // Keep updating the max
        curr_max = max(curr_max, maxi.back());
    }
    cout << "Lexicographically smallest permutation is : ";
    for (auto i : mini)
        cout << i << " ";
    cout << endl;
    cout << "Lexicographically largest permutation is : ";
    for (auto i : maxi)
        cout << i << " ";
    cout << endl;
}
 
// Driver Code
int main()
{
    vector<int> A{ 2, 4, 4, 4, 6, 6 };
 
    // Function call
    findMinMaxPermutation(A);
    return 0;
}

Java

/*package whatever //do not write package name here */
 
import java.io.*;
import java.util.*;
class GFG
{
   
  // Function to return the max array of
  // minimum and maximum permutation
  // satisfying A
  public static void
    findMinMaxPermutation(List<Integer> A)
  {
    int n = A.size();
     
    // set<Integer> s;
    HashSet<Integer> s = new HashSet<Integer>();
    List<Integer> mini = new ArrayList<Integer>();
    List<Integer> maxi = new ArrayList<Integer>();
 
    // Pushing all the elements into set till n
    for (int i = 1; i < n + 1; i++)
      s.add(i);
    int curr_max = 0;
    for (int i = 0; i < n; i++) {
      int number = Integer.MAX_VALUE;
       
      // If curr_max is less
      if (curr_max < A.get(i)) {
        number = A.get(i);
      }
 
      // Choosing the smallest element less than A[i]
      else
        for (int var : s) {
 
          // For elements in Set
          if (var < number)
 
            // Update the minimum element
            number = var;
        }
 
      // Erasing from set
      s.remove(number);
 
      // Pushing the elements to vector
      mini.add(number);
 
      // Keep updating the max
      curr_max = Math.max(curr_max,
                          mini.get(mini.size() - 1));
    }
    curr_max = 0;
 
    // Pushing all the elements into set till n
    for (int i = 1; i < n + 1; i++)
      s.add(i);
    for (int i = 0; i < n; i++) {
      int number = 0;
 
      // If curr_max is less
      if (curr_max < A.get(i))
        number = A.get(i);
 
      // Choosing the bigger element but less than
      // A[i]
      else {
        for (int num : s) {
          if (num <= A.get(i))
            number = Math.max(number, num);
        }
      }
 
      // Erasing from set
      s.remove(number);
 
      // Pushing the elements to vector
      maxi.add(number);
 
      // Keep updating the max
      curr_max = Math.max(curr_max,
                          maxi.get(maxi.size() - 1));
    }
    System.out.print(
      "Lexicographically smallest permutation is : ");
    for (int i : mini)
      System.out.print(i + " ");
    System.out.println("");
    System.out.print(
      "Lexicographically largest permutation is : ");
    for (int i : maxi)
      System.out.print(i + " ");
    System.out.println("");
  }
 
  public static void main(String[] args)
  {
    List<Integer> A = new ArrayList<Integer>(
      Arrays.asList(2, 4, 4, 4, 6, 6));
 
    // Function call
    findMinMaxPermutation(A);
  }
}
 
// This code is contributed by akashish__

Python3

# Python code for the above approach
 
# import the module
import math
 
# Function to return the max array of
# minimum and maximum permutation satisfying A
def findMinMaxPermutation(A):
    n = len(A)
 
    # set s
    s = set()
    mini = []
    maxi = []
 
    # Pushing all the elements into set till n
    for i in range(1, n+1):
        s.add(i)
 
    curr_max = 0
    for i in range(n):
        number = math.inf
 
        # If curr_max is less
        if(curr_max < A[i]):
            number = A[i]
 
        # Choosing the smallest element less than A[i]
        else:
            for var in s:
                # For elements in Set
                if(var < number):
                    # Update the minimum element
                    number = var
 
        # Erasing from set
        s.remove(number)
 
        # Pushing the elements to vector
        mini.append(number)
 
        # Keep updating the max
        curr_max = max(curr_max, mini[len(mini)-1])
 
    curr_max = 0
 
    # Pushing all the elements into set till n
    for i in range(1, n+1):
        s.add(i)
 
    for i in range(n):
        number = 0
 
        # If curr_max is less
        if(curr_max < A[i]):
            number = A[i]
 
        # Choosing the bigger element but less than A[i]
        else:
            for num in s:
                if(num <= A[i]):
                    number = max(number, num)
 
        # Erasing from set
        s.remove(number)
 
        # Pushing the elements to vector
        maxi.append(number)
 
        # Keep updating the max
        curr_max = max(curr_max, maxi[len(maxi)-1])
 
    print("Lexicographically smallest permutation is :", end=" ")
    for i in mini:
        print(i, end=" ")
    print()
    print("Lexicographically largest permutation is :", end=" ")
    for i in maxi:
        print(i, end=" ")
    print()
 
 
A = [2, 4, 4, 4, 6, 6]
 
# Function call
findMinMaxPermutation(A)
 
# This code is contributed by lokeshmvs21.

C#

// C# code for the above approach
 
using System;
using System.Collections.Generic;
 
public class GFG {
 
  // Function to return the max array of minimum and
  // maximum permutation satisfying A
  static void findMinMaxPermutation(List<int> A)
  {
    int n = A.Count;
 
    // set<Integer> s;
    HashSet<int> s = new HashSet<int>();
    List<int> mini = new List<int>();
    List<int> maxi = new List<int>();
 
    // Pushing all the elements into set till n
    for (int i = 1; i < n + 1; i++) {
      s.Add(i);
    }
 
    int curr_max = 0;
    for (int i = 0; i < n; i++) {
      int number = Int32.MaxValue;
 
      // If curr_max is less
      if (curr_max < A[i]) {
        number = A[i];
      }
 
      // Choosing the smallest element less than A[i]
      else {
        foreach(var Var in s)
        {
          // For elements in Set
          if (Var < number) {
            // Update the minimum element
            number = Var;
          }
        }
      }
 
      // Erasing from set
      s.Remove(number);
 
      // Pushing the elements to vector
      mini.Add(number);
 
      // Keep updating the max
      curr_max
        = Math.Max(curr_max, mini[mini.Count - 1]);
    }
    curr_max = 0;
 
    // Pushing all the elements into set till n
    for (int i = 1; i < n + 1; i++) {
      s.Add(i);
    }
 
    for (int i = 0; i < n; i++) {
      int number = 0;
 
      // If curr_max is less
      if (curr_max < A[i]) {
        number = A[i];
      }
 
      // Choosing the bigger element but less than
      // A[i]
      else {
        foreach(var num in s)
        {
          if (num <= A[i]) {
            number = Math.Max(number, num);
          }
        }
      }
 
      // Erasing from set
      s.Remove(number);
 
      // Pushing the elements to vector
      maxi.Add(number);
 
      // Keep updating the max
      curr_max
        = Math.Max(curr_max, maxi[maxi.Count - 1]);
    }
 
    Console.Write(
      "Lexicographically smallest permutation is : ");
    for (int i = 0; i < mini.Count; i++) {
      Console.Write(mini[i] + " ");
    }
    Console.WriteLine("");
    Console.Write(
      "Lexicographically largest permutation is : ");
    for (int i = 0; i < maxi.Count; i++) {
      Console.Write(maxi[i] + " ");
    }
    Console.WriteLine("");
  }
 
  static public void Main()
  {
 
    // Code
    List<int> A = new List<int>() { 2, 4, 4, 4, 6, 6 };
 
    // Function call
    findMinMaxPermutation(A);
  }
}
 
// This code is contributed by lokeshmvs21.

Javascript

// JavaScript code to implement the approach
 
// Function to return the max array of
// minimum and maximum permutation
// satisfying A
function findMinMaxPermutation(A)
{
    let n = A.length;
    let s = new Set();
    let mini = [];
    let maxi = [];
 
    // Pushing all the elements into set till n
    for (let i = 1; i < n + 1; i++)
        s.add(i);
    let curr_max = 0;
    for (let i = 0; i < n; i++) {
        let number=0;
 
        // If curr_max is less
        if (curr_max < A[i]) {
            number = A[i];
        }
 
        // Choosing the smallest element less than A[i]
        else
            number = Math.min(...s);
 
        // Erasing from set
        s.delete(number);
 
        // Pushing the elements to mini array
        mini.push(number);
 
        // Keep updating the max
        curr_max = Math.max(curr_max, mini[mini.length-1]);
    }
    curr_max = 0;
 
    // Pushing all the elements into set till n
    for (let i = 1; i < n + 1; i++)
        s.add(i);
    for (let i = 0; i < n; i++) {
        let number=0;
 
        // If curr_max is less
        if (curr_max < A[i])
            number = A[i];
 
        // Choosing the bigger element but less than A[i]
        else
            {
                for(let num of s)
                {
                    if(num<=A[i])
                    number=Math.max(number, num);
                }
            }
 
        // Erasing from set
        s.delete(number);
 
        // Pushing the elements to maxi array
        maxi.push(number);
 
        // Keep updating the max
        curr_max = Math.max(curr_max, maxi[maxi.length-1]);
    }
    console.log("Lexicographically smallest permutation is : " + mini);
    console.log("Lexicographically largest permutation is : " + maxi);
     
}
 
// Driver Code
    let A = [2, 4, 4, 4, 6, 6 ];
 
    // Function call
    findMinMaxPermutation(A);
 
    // This code is contributed by Ishan Khandelwal

Output

Lexicographically smallest permutation is : 2 4 1 3 6 5 
Lexicographically largest permutation is : 2 4 3 1 6 5

Time Complexity: N* logN
Auxiliary Space: O(N)


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Minimize Array sum by replacing an element with GCD Minimize Array sum by replacing an element with GCD
Minimize operations to empty Array by deleting two unequal elements or one element Minimize operations to empty Array by deleting two unequal elements or one element
Count ways to make given Subarray strictly increasing by replacing one element for Q queries Count ways to make given Subarray strictly increasing by replacing one element for Q queries
Find the MEX of given Array Find the MEX of given Array
Minimum swaps to minimize the sum of first K elements of the Permutation Minimum swaps to minimize the sum of first K elements of the Permutation

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje