Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
4.
Pseudocode for finding the LCS in K permutations
5.
Code in Python3
5.1.
Time Complexity
5.2.
Space Complexity
6.
Frequently Asked Questions
7.
Key Takeaways
Last Updated: Mar 27, 2024

Finding the Longest Common Subsequence (LCS) in given K permutations

Author HET FADIA
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

This article aims to familiarise you with the Longest Common Subsequence in K permutation arrays. 

To brush up on your knowledge of LCS, you can read the article longest common subsequence on Coding Ninjas Studio.

Let’s see the problem statement in the next section.

Problem Statement

Each array consists of K arrays which are permutations from 1 to N.  

We have to return the LCS among all the K arrays, i.e. we return the length of the largest common subsequence present in all the K permutations.

Note: Throughout this article, we will be using the term “LCS”, a short form for Longest Common Subsequence.

 

Now, let us see a few of the examples of the problem statement:

1. arr =  [[1,2,3],[1,3,2],[2,1,3]] 

Output: 2

Explanation: We can see that [1,3] is a subsequence present in all the 3 permutations. Thus the length of [1,3], i.e. 2, is the answer.

2. arr =  [[1,2,3,4],[4,3,2,1]]

Output: 1

Explanation: We can see that the largest subsequence present in both the permutations are [1], [2], [3] and [4]. Since all of them have length 1, our output will be 1.

3. arr =  [[1,2,3],[1,2,3],[1,2,3]]

Output: 3

Explanation: The [1,2,3] is present in all the 3 permutations. Thus we return 3.

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)
You can also try this code with Online Python Compiler
Run Code

Output

2

Time Complexity

The time complexity of the above algorithm is O(Nx 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(Nx K).

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

Thus final time complexity is O(N*K) + O(Nx K) + O(N). The O(Nx K) dominates, so time complexity is O(Nx 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(2x N x K) because there are 2subsets, 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!!!

 

Live masterclass