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!