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 itvoid 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 Codeint main(){Â Â Â Â int K = 7;Â Â Â Â vector<int> arr = { 6, 4, 2, 1 };Â
    // Function Call    findPermutation(K, arr);Â
    return 0;} |
Java
// Java program for the above approachimport java.util.*;Â
class GFG{Â
// Function to find the lexicographically// smallest permutation such that the// given array is a subsequence of itstatic 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 Codepublic 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 itdef 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 Codeif __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 approachusing System;using System.Collections;class GFG{Â
// Function to find the lexicographically// smallest permutation such that the// given array is a subsequence of itstatic 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 Codepublic 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
