Lexicographically smallest permutation number up to K having given array as a subsequence

0 0 7 minutes read

Given an integer K and an array arr[] having N pairwise distinct integers in the range [1, K], the task is to find the lexicographically smallest permutation of the first K positive integers such that the given array arr[] is a subsequence of the permutation.

Examples:

Input: arr[] = {1, 3, 5, 7}, K = 8
Output: 1 2 3 4 5 6 7 8
Explanation: {1, 2, 3, 4, 5, 6, 7, 8} is the lexicographically smallest permutation of the first 8 positive integers such that the given array {1, 3, 5, 7} is also a subsequence of the permutation.

Input: arr[] = {6, 4, 2, 1}, K=7
Output: 3 5 6 4 2 1 7

Approach: The given problem can be solved by using a greedy approach. Below are the steps to follow:

Create a vector missing[] that stores the integers in the range [1, K] in increasing order that are not present in the given array arr[] using the approach discussed in this article.
Create two pointers p1 and p2 which store the current index in arr[] and missing[] respectively. Initially, both are equal to 0.
Greedily take and store the minimum of arr[p1] and missing [p2] into a vector, say ans[] and increment the respective pointer to the next position till the count of the stored integers is less than K.
In order to make things easier, append INT_MAX at the end of the array missing[] and arr[] which will avoid getting out of bounds.
After completing the above steps, all the values stored in the ans[] is the required result.

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
// smallest permutation such that the
// given array is a subsequence of it
void findPermutation(int K, vector<int> arr)
{
    // Stores the missing elements in
    // arr in the range [1, K]
    vector<int> missing;
 
    // Stores if the ith element is
    // present in arr or not
    vector<bool> visited(K + 1, 0);
 
    // Loop to mark all integers present
    // in the array as visited
    for (int i = 0; i < arr.size(); i++) {
        visited[arr[i]] = 1;
    }
 
    // Loop to insert all the integers
    // not visited into missing
    for (int i = 1; i <= K; i++) {
        if (!visited[i]) {
            missing.push_back(i);
        }
    }
    // Append INT_MAX at end in order
    // to prevent going out of bounds
    arr.push_back(INT_MAX);
    missing.push_back(INT_MAX);
 
    // Pointer to the current element
    int p1 = 0;
 
    // Pointer to the missing element
    int p2 = 0;
 
    // Stores the required permutation
    vector<int> ans;
 
    // Loop to construct the permutation
    // using greedy approach
    while (ans.size() < K) {
 
        // If missing element is smaller
        // that the current element insert
        // missing element
        if (arr[p1] < missing[p2]) {
            ans.push_back(arr[p1]);
            p1++;
        }
 
        // Insert current element
        else {
            ans.push_back(missing[p2]);
            p2++;
        }
    }
 
    // Print the required Permutation
    for (int i = 0; i < K; i++) {
        cout << ans[i] << " ";
    }
}
 
// Driver Code
int main()
{
    int K = 7;
    vector<int> arr = { 6, 4, 2, 1 };
 
    // Function Call
    findPermutation(K, arr);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the lexicographically
// smallest permutation such that the
// given array is a subsequence of it
static void findPermutation(int K, Vector<Integer> arr)
{
    // Stores the missing elements in
    // arr in the range [1, K]
    Vector<Integer> missing = new Vector<Integer>();
 
    // Stores if the ith element is
    // present in arr or not
    boolean visited[] = new boolean[K + 1];
 
    // Loop to mark all integers present
    // in the array as visited
    for (int i = 0; i < arr.size(); i++) {
        visited[arr.get(i)] = true;
    }
 
    // Loop to insert all the integers
    // not visited into missing
    for (int i = 1; i <= K; i++) {
        if (!visited[i]) {
            missing.add(i);
        }
    }
    // Append Integer.MAX_VALUE at end in order
    // to prevent going out of bounds
    arr.add(Integer.MAX_VALUE);
    missing.add(Integer.MAX_VALUE);
 
    // Pointer to the current element
    int p1 = 0;
 
    // Pointer to the missing element
    int p2 = 0;
 
    // Stores the required permutation
    Vector<Integer> ans = new Vector<Integer>();
 
    // Loop to construct the permutation
    // using greedy approach
    while (ans.size() < K) {
 
        // If missing element is smaller
        // that the current element insert
        // missing element
        if (arr.get(p1) < missing.get(p2)) {
            ans.add(arr.get(p1));
            p1++;
        }
 
        // Insert current element
        else {
            ans.add(missing.get(p2));
            p2++;
        }
    }
 
    // Print the required Permutation
    for (int i = 0; i < K; i++) {
        System.out.print(ans.get(i)+ " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int K = 7;
    Integer []a = {6, 4, 2, 1};
    Vector<Integer> arr = new Vector<>(Arrays.asList(a));
 
    // Function Call
    findPermutation(K, arr);
 
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python program for the above approach
 
# Function to find the lexicographically
# smallest permutation such that the
#  given array is a subsequence of it
def findPermutation(K, arr):
   
    # Stores the missing elements in
        # arr in the range [1, K]
    missing = []
 
    # Stores if the ith element is
    # present in arr or not
    visited = [0]*(K+1)
 
    # Loop to mark all integers present
    # in the array as visited
    for i in range(4):
        visited[arr[i]] = 1
 
    # Loop to insert all the integers
    # not visited into missing
    for i in range(1, K+1):
        if(not visited[i]):
            missing.append(i)
 
    # Append INT_MAX at end in order
        # to prevent going out of bounds
    INT_MAX = 2147483647
    arr.append(INT_MAX)
    missing.append(INT_MAX)
 
    # Pointer to the current element
    p1 = 0
 
    # Pointer to the missing element
    p2 = 0
 
    # Stores the required permutation
    ans = []
 
    # Loop to construct the permutation
    # using greedy approach
 
    while (len(ans) < K):
        # If missing element is smaller
                # that the current element insert
        # missing element
        if (arr[p1] < missing[p2]):
            ans.append(arr[p1])
            p1 = p1 + 1
 
        # Insert current element
        else:
            ans.append(missing[p2])
            p2 = p2 + 1
 
    # Print the required Permutation
    for i in range(0, K):
        print(ans[i], end=" ")
 
# Driver Code
if __name__ == "__main__":
    K = 7
    arr = [6, 4, 2, 1]
 
    # Function Call
    findPermutation(K, arr)
     
    # This code is contributed by rakeshsahni

C#

// C# program for the above approach
using System;
using System.Collections;
class GFG{
 
// Function to find the lexicographically
// smallest permutation such that the
// given array is a subsequence of it
static void findPermutation(int K, ArrayList arr)
{
   
    // Stores the missing elements in
    // arr in the range [1, K]
    ArrayList missing = new ArrayList();
 
    // Stores if the ith element is
    // present in arr or not
    bool [] visited = new bool[K + 1];
 
    // Loop to mark all integers present
    // in the array as visited
    for (int i = 0; i < arr.Count; i++) {
        visited[(int)arr[i]] = true;
    }
 
    // Loop to insert all the integers
    // not visited into missing
    for (int i = 1; i <= K; i++) {
        if (!visited[i]) {
            missing.Add(i);
        }
    }
    // Append Int32.MaxValue at end in order
    // to prevent going out of bounds
    arr.Add(Int32.MaxValue);
    missing.Add(Int32.MaxValue);
 
    // Pointer to the current element
    int p1 = 0;
 
    // Pointer to the missing element
    int p2 = 0;
 
    // Stores the required permutation
    ArrayList ans = new ArrayList();
 
    // Loop to construct the permutation
    // using greedy approach
    while (ans.Count < K) {
 
        // If missing element is smaller
        // that the current element insert
        // missing element
        if ((int)arr[p1] < (int)missing[p2]) {
            ans.Add(arr[p1]);
            p1++;
        }
 
        // Insert current element
        else {
            ans.Add(missing[p2]);
            p2++;
        }
    }
 
    // Print the required Permutation
    for (int i = 0; i < K; i++) {
        Console.Write(ans[i]+ " ");
    }
}
 
// Driver Code
public static void Main()
{
    int K = 7;
    int [] a = {6, 4, 2, 1};
    ArrayList arr = new ArrayList(a);
 
    // Function Call
    findPermutation(K, arr);
}
}
 
// This code is contributed by ihritik.

Javascript

<script>
    // JavaScript program for the above approach
 
    // Function to find the lexicographically
    // smallest permutation such that the
    // given array is a subsequence of it
    const findPermutation = (K, arr) => {
     
        // Stores the missing elements in
        // arr in the range [1, K]
        let missing = [];
 
        // Stores if the ith element is
        // present in arr or not
        let visited = new Array(K + 1).fill(0);
 
        // Loop to mark all integers present
        // in the array as visited
        for (let i = 0; i < arr.length; i++) {
            visited[arr[i]] = 1;
        }
 
        // Loop to insert all the integers
        // not visited into missing
        for (let i = 1; i <= K; i++) {
            if (!visited[i]) {
                // missing.push_back(i);
                missing.push(i);
            }
        }
        // Append INT_MAX at end in order
        // to prevent going out of bounds
        const INT_MAX = 2147483647;
        arr.push(INT_MAX);
        missing.push(INT_MAX);
 
        // Pointer to the current element
        let p1 = 0;
 
        // Pointer to the missing element
        let p2 = 0;
 
        // Stores the required permutation
        let ans = [];
 
        // Loop to construct the permutation
        // using greedy approach
        while (ans.length < K) {
 
            // If missing element is smaller
            // that the current element insert
            // missing element
            if (arr[p1] < missing[p2]) {
                ans.push(arr[p1]);
                p1++;
            }
 
            // Insert current element
            else {
                ans.push(missing[p2]);
                p2++;
            }
        }
 
        // Print the required Permutation
        for (let i = 0; i < K; i++) {
            document.write(`${ans[i]} `);
        }
    }
 
    // Driver Code
    let K = 7;
    let arr = [6, 4, 2, 1];
 
    // Function Call
    findPermutation(K, arr);
     
    // This code is contributed by rakeshsahni.
</script>

Output:

3 5 6 4 2 1 7

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 zambiatek!