Given K permutations of numbers from 1 to N in a 2D array arr[][]. The task is to find the longest common subsequence of these K permutations.
Examples:
Input: N = 4, K = 3
arr[][] = {{1, 4, 2, 3},
{4, 1, 2, 3},
{1, 2, 4, 3}}
Output: 3
Explanation: Longest common subsequence is {1, 2, 3} which has length 3.Input: N = 6, K = 3,
arr[][] = {{2, 5, 1, 4, 6, 3},
{5, 1, 4, 3, 2, 6},
{5, 4, 2, 6, 3, 1}}
Output: 3
Explanation: Longest common subsequence is {5, 4, 6} which has length 3.
Approach: This problem is an extension of longest common subsequence. The solution is based on the concept of dynamic programming. Follow the steps below:
- Create a 2D array(pos[][]) to store position of all the numbers from 1 to N in each sequence, where pos[i][j] denotes position of value j in ith sequence.
- Initialize an array(dp[]) where dp[i] stores the longest common subsequence ending at position i.
- Consider the first sequence as reference and for each element of the first sequence check the relative positions of them in other sequences.
- Iterate over all possible indices j such that j < i and see if value at index i of the first sequence can be appended to the longest increasing subsequence ending at j.
- This is done by checking if position of the number arr[0][j] is less than equal to position of the value arr[0][i] in all the permutations. Then the value at arr[0][i] can be appended to the sequence ending at position j.
- Consider the first sequence as reference and for each element of the first sequence check the relative positions of them in other sequences.
- So the recurrence is dp[i] = max(dp[i], 1 + dp[j]).
- The maximum value from the array dp[] is the answer.
See the following illustration:
Illustration:
Take the following example:
N = 4, K = 3, arr[][] = {{1, 4, 2, 3},
{4, 1, 2, 3},
{1, 2, 4, 3}}
- Form the position array: pos[][] = {{1, 3, 4, 2},
{2, 3, 4, 1},
{1, 2, 4, 3}}
In first sequence 1 is in 1st position, 2 in 3rd position, 3 in 4th and 4 in 2nd position. And so on for the other sequences.- Initialize dp[] array: The dp[] array is initialized and it initially dp[] = {0, 0, 0, 0}
- Reference sequence: The first sequence i{1, 4, 2, 3} is used as the reference sequence i.e. relative positions of elements in other sequences are checked according to this one.
- For i = 1: dp[1] = 1 because any sequence of length 1 is a increasing sequence. Now dp[] = {1, 0, 0, 0}
- For i = 2: Now relative position of 4 and 1 will be checked in all the 3 sequences. In 2nd sequence and 3rd sequence the relative position is not maintained. So dp[2] = dp[1]. Now dp[] = {1, 1, 0, 0}.
- For i = 3: Relative positions of (1, 4, 2) are checked.
When j = 1 i.e. value relative position of 1 and 2 are checked it satisfies the condition pos[ind][arr[1][1]] < pos[ind][arr[1][3]] for all ind in range [1, K]. So dp[3] = max(dp[3], dp[1]+1) = max(0, 2) = 2.
Now dp[] = {1, 1, 2, 0}- For i = 4: Here also when j = 3, then pos[ind][arr[1][3]] < pos[ind][arr[1][4]] for all ind in range [1, K]. So the 4th element of 1st sequence can be appended in the longest increasing subsequence ending at 3rd index. dp[4] = dp[3] + 1 = 2 + 1 = 3.
Now dp[] = {1, 1, 2, 3}- The maximum value in dp[] is 3. Therefore, the maximum length of the longest increasing subsequence is 3.
Note: 0 based indexing is used in the actual implementation. Here 1 based indexing is used for easy understanding
Below is the implementation of the above approach.
C++
// C++ code to find the longest common// sub sequence of k permutations.#include <bits/stdc++.h>using namespace std;// Function to find the longest common// sub sequence of k permutations.int findLcs(vector<vector<int>> &arr, int n, int k){ // Variable to keep track of the length // of the longest common sub sequence int maxLen = 0; // position array to keep track // of position of elements // in each permutation int pos[k][n]; // Array to store the length of LCS int dp[n]; for (int i = 0; i < k; i++) { for (int j = 0; j < n; j++) { pos[i][arr[i][j] - 1] = j; } } // Loop to calculate the LCS // of all the permutations for (int i = 0; i < n; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { bool good = true; for (int p = 0; p < k; p++) { if (pos[p][arr[0][j] - 1] > pos[p][arr[0][i] - 1]) { good = false; break; } } if (good) { dp[i] = max(dp[i], 1 + dp[j]); maxLen = max(maxLen, dp[i]); } } } return maxLen;}// Driver codeint main(){ vector<vector<int>> arr = {{2, 5, 1, 4, 6, 3}, {5, 1, 4, 3, 2, 6}, {5, 4, 2, 6, 3, 1}}; int N = arr[0].size(); int K = 3; // Function Call cout << findLcs(arr, N, K); return 0;} |
Java
// Java code to find the longest common// sub sequence of k permutations.import java.util.*;class GFG{// Function to find the longest common// sub sequence of k permutations.static int findLcs(int[][]arr, int n, int k){ // Variable to keep track of the length // of the longest common sub sequence int maxLen = 0; // position array to keep track // of position of elements // in each permutation int [][]pos = new int[k][n]; // Array to store the length of LCS int []dp = new int[n]; for (int i = 0; i < k; i++) { for (int j = 0; j < n; j++) { pos[i][arr[i][j] - 1] = j; } } // Loop to calculate the LCS // of all the permutations for (int i = 0; i < n; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { boolean good = true; for (int p = 0; p < k; p++) { if (pos[p][arr[0][j] - 1] > pos[p][arr[0][i] - 1]) { good = false; break; } } if (good) { dp[i] = Math.max(dp[i], 1 + dp[j]); maxLen = Math.max(maxLen, dp[i]); } } } return maxLen;}// Driver codepublic static void main(String[] args){ int[][] arr = {{2, 5, 1, 4, 6, 3}, {5, 1, 4, 3, 2, 6}, {5, 4, 2, 6, 3, 1}}; int N = arr[0].length; int K = 3; // Function Call System.out.print(findLcs(arr, N, K));}}// This code is contributed by shikhasingrajput |
Python3
# Python code for the above approach# Function to find the longest common# sub sequence of k permutations.def findLcs(arr, n, k): # Variable to keep track of the length # of the longest common sub sequence maxLen = 0 # position array to keep track # of position of elements # in each permutation pos = [0] * k for i in range(len(pos)): pos[i] = [0] * n # Array to store the length of LCS dp = [0] * n for i in range(k): for j in range(n): pos[i][arr[i][j] - 1] = j # Loop to calculate the LCS # of all the permutations for i in range(n): dp[i] = 1 for j in range(i): good = True for p in range(k): if (pos[p][arr[0][j] - 1] > pos[p][arr[0][i] - 1]): good = False break if (good): dp[i] = max(dp[i], 1 + dp[j]) maxLen = max(maxLen, dp[i]) return maxLen# Driver codearr = [[2, 5, 1, 4, 6, 3], [5, 1, 4, 3, 2, 6], [5, 4, 2, 6, 3, 1]]N = len(arr[0])K = 3# Function Callprint(findLcs(arr, N, K))# This code is contributed by Saurabh Jaiswal |
C#
// C# code to find the longest common// sub sequence of k permutations.using System;class GFG { // Function to find the longest common // sub sequence of k permutations. static int findLcs(int[, ] arr, int n, int k) { // Variable to keep track of the length // of the longest common sub sequence int maxLen = 0; // position array to keep track // of position of elements // in each permutation int[, ] pos = new int[k, n]; // Array to store the length of LCS int[] dp = new int[n]; for (int i = 0; i < k; i++) { for (int j = 0; j < n; j++) { pos[i, arr[i, j] - 1] = j; } } // Loop to calculate the LCS // of all the permutations for (int i = 0; i < n; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { bool good = true; for (int p = 0; p < k; p++) { if (pos[p, arr[0, j] - 1] > pos[p, arr[0, i] - 1]) { good = false; break; } } if (good) { dp[i] = Math.Max(dp[i], 1 + dp[j]); maxLen = Math.Max(maxLen, dp[i]); } } } return maxLen; } // Driver code public static void Main(string[] args) { int[, ] arr = { { 2, 5, 1, 4, 6, 3 }, { 5, 1, 4, 3, 2, 6 }, { 5, 4, 2, 6, 3, 1 } }; int N = arr.GetLength(1); int K = 3; // Function Call Console.WriteLine(findLcs(arr, N, K)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach // Function to find the longest common // sub sequence of k permutations. function findLcs(arr, n, k) { // Variable to keep track of the length // of the longest common sub sequence let maxLen = 0; // position array to keep track // of position of elements // in each permutation let pos = new Array(k); for (let i = 0; i < pos.length; i++) { pos[i] = new Array(n) } // Array to store the length of LCS let dp = new Array(n); for (let i = 0; i < k; i++) { for (let j = 0; j < n; j++) { pos[i][arr[i][j] - 1] = j; } } // Loop to calculate the LCS // of all the permutations for (let i = 0; i < n; i++) { dp[i] = 1; for (let j = 0; j < i; j++) { let good = true; for (let p = 0; p < k; p++) { if (pos[p][arr[0][j] - 1] > pos[p][arr[0][i] - 1]) { good = false; break; } } if (good) { dp[i] = Math.max(dp[i], 1 + dp[j]); maxLen = Math.max(maxLen, dp[i]); } } } return maxLen; } // Driver code let arr = [[2, 5, 1, 4, 6, 3], [5, 1, 4, 3, 2, 6], [5, 4, 2, 6, 3, 1]]; let N = arr[0].length; let K = 3; // Function Call document.write(findLcs(arr, N, K)); // This code is contributed by Potta Lokesh </script> |
Output
3
Time Complexity: O(N2 * K)
Auxiliary Space: O(N * K)
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!
