## Approach

Our approach is simple. First, we calculate the position array in the above code. The position array helps us find the position of an element in the ith permutation.

Next, we make a dp array and initialise it with 1.

Here dp[i] gives us the length of the longest subsequence in arr[0][ 0 … i] which is also a subsequence in arr[1], arr[2] and so on.

Consider the first example **arr = [[1,2,3],[1,3,2],[2,1,3]].**

Here initially dp=[1,1,1].

Now we check for arr[0][0]=1.

As [1] is present in every permutations dp[0]=1.

The we check for arr[0][0…1] = [1,2].

The largest subset of [1,2] present in every permutation are [1] and [2].

So dp[1]=1.

Finally we check for [1,2,3].The [1,3] is present in every permutation. So we set dp[2] as 2.

Thus max(dp)=2 is our final answer.

Below are the steps for the implementation

1. First, we initialise the position array

2. Next, we iterate i from 1 to N. In the ith iteration, we iterate j from 1 to i-1. Next, we check if the position of every arr[0][i] is greater than arr[0][j] in every permutations and update the dp[i].

3. Finally, we return the max of the dp array.

## Pseudocode for finding the LCS in K permutations

```
DEFINE FUNCTION get_position_array(arr):
k=length of (arr)
n=length of (arr[0])
pos_arr=[[0 FOR j IN range(n)] FOR i IN range(k)]
FOR i IN range(k):
FOR j IN range(n):
pos_arr[i][arr[i][j]-1]=j
RETURN pos_arr
DEFINE FUNCTION get_lcs(arr):
k=len(arr)
n=len(arr[0])
pos_arr=get_position_array(arr)
dp_arr=[1 FOR i IN range(n)]
FOR i IN range(n):
FOR j IN range(i):
FOR l IN range(k):
IF pos_arr[l][arr[0][i]-1]<pos_arr[l][arr[0][j]-1]:
break
ELSE:
dp_arr[i]=max(dp_arr[i],dp_arr[j]+1)
RETURN max(dp_arr)
```

## Code in Python3

```
def get_position_array(arr):
k=len(arr)
n=len(arr[0])
# we make the pos array which can store k arrays having position of each permutation
pos_arr=[[0 for j in range(n)] for i in range(k)]
for i in range(k):
for j in range(n):
""" the position of arr[i][j] in the array is j
As here our indexing is 0 based but the permutation is 1 to n
we subtract 1 from arr[i][j]
Thus pos_arr[i][arr[i][j]-1]=j
So in the future when we need the position of arr[i][j] in ith permutation
we can get by pos[i][arr[i][j]-1]
"""
pos_arr[i][arr[i][j]-1]=j
# print("The position array is",pos_arr)
return pos_arr
def get_lcs(arr):
k=len(arr)
n=len(arr[0])
pos_arr=get_position_array(arr)
"""
now we make a dp array to store the lcs till ith position.
Any integer from 1 to n is present in all the k permutations.
so the answers is at least 1
So we inititalize dp array with all 1.
"""
dp_arr=[1 for i in range(n)]
for i in range(n):
for j in range(i):
for l in range(k):
"""
Here we have computed the dp[j].
We are using the precalculated dp[j] to calculate dp[i].
consider that there were 2 subarray found on dp[j].
If again the arr[0][i] has higher position than arr[0][j] in all permutations
then we have found a new subarray of length 3 present in all those permutations.
Thus dp[i] will be max(dp[i],dp[j]+1)
Here the reference array is 0.
"""
if pos_arr[l][arr[0][i]-1]<pos_arr[l][arr[0][j]-1]:
# if the condition fails at any one of the permutation then we break and do not update the dp[j]
break
else:
"""
Here we have used for-else loop.
This else statement is only executed when we do not reach the above break statement in the if condition.
So if none of the if condition satisfies then no if will be executed and this else will be executed.
"""
dp_arr[i]=max(dp_arr[i],dp_arr[j]+1)
# print("The dp array is",dp_arr)
return max(dp_arr)
arr = [[1,2,3],[1,3,2],[2,1,3]]
answer=get_lcs(arr)
print(answer)
```

Output

`2`

### Time Complexity

The time complexity of the above algorithm is O(N^{2 }x K).

The time complexity for making the get_position_array function is O(N*K).

There are three “for loops” in the above code. The first for loop runs from 1 to N. The second runs from 1 to i-1. The third loop runs from 1 to K.

Thus, time complexity = O(N^{2 }x K).

Again finding max(dp) takes O(N) time.

Thus final time complexity is O(N*K) + O(N^{2 }x K) + O(N). The O(N^{2 }x K) dominates, so time complexity is O(N^{2 }x K).

### Space Complexity

The space complexity of the above code is O(N*K).

The space complexity for making the get_position_array function is O(N*K), as we make an array of N*K size.

Then the dp array takes O(N) size.

Thus dominating space complexity is O(N*K).

**Frequently Asked Questions**

**1. What could be the brute force approach?**

In the brute force approach, we will check for each subset that makes a subsequence. Then among those subsets, we will output the length of the largest subset, which was also a subsequence. Here the time complexity will be O(2^{N }x N x K) because there are 2^{N }subsets, and for each subset, we are checking if they make subsequence in O(N x K).

**2. Why is the pos_array calculated in the above code?**

We are using the position array to get the position of an element in the lth permutation. Using the position array, we can quickly get the element's position and quickly check if it makes an LCS or not.

**3. What is the best case time complexity of the above program?**

In the best case the condition if pos_arr[l][arr[0][i]-1]<pos_arr[l][arr[0][j]-1]: will be false everytime and thus the for l in range(k): will execute only once.

Thus the time complexity will be O(N*K) in the best case.

Few such examples of such cases are arr=[[1,2,3],[3,2,1],[1,2,3]] and arr=[[1,2],[2,1]]

**Key Takeaways**

The article helps us understand how to find the Longest Common Subsequence in python. We also understand how to calculate the LCS among K permutations efficiently. The code contains comments for better understanding. You can also copy the code and run it on your system on multiple inputs to understand the approach better. You can also uncomment print statements in the code to print them and understand the code better. If you would like to learn more, try the Longest Palindromic Subsequence problem.

Check out __Coding Ninjas Studio__ to learn more about competitive programming, DSA, attempt mock tests, interview preparation and much more.

Happy Learning!!!