Given two arrays firstArr[], consisting of distinct elements only, and secondArr[], the task is to find the length of LCS between these 2 arrays.
Examples:
Input: firstArr[] = {3, 5, 1, 8}, secondArr[] = {3, 3, 5, 3, 8}
Output: 3.
Explanation: LCS between these two arrays is {3, 5, 8}.Input : firstArr[] = {1, 2, 1}, secondArr[] = {3}
Output: 0
Naive Approach: Follow the steps below to solve the problem using the simplest possible approach:
- Initialize an array dp[][] such that dp[i][j] stores longest common subsequence of firstArr[ :i] and secondArr[ :j].
- Traverse the array firstArr[] and for every array element of the array firstArr[], traverse the array secondArr[].
- If firstArr[i] = secondArr[j]: Set dp[i][j] = dp[i – 1][j – 1] + 1.
- Otherwise: Set dp[i][j] = max(dp[ i – 1][j], dp[i][j – 1]).
Time Complexity: O(N * M), where N and M are the sizes of the arrays firstArr[] and secondArr[] respectively.
Auxiliary Space: O(N * M)
Efficient Approach: To optimize the above approach, follow the steps below:
- Initialize a Map, say mp, to store the mappings map[firstArr[i]] = i, i.e. map elements of the first array to their respective indices.
- Since the elements which are present in secondArr[] but not in the firstArr[] are not useful at all, as they can never be a part of a common subsequence, traverse the array secondArr[] andfor each array element, check if it is present in the Map or not.
- If found to be true, push map[secondArr[i]] into a temporary Array. Otherwise ignore it.
- Find the Longest Increasing Subsequence (LIS) of the obtained temporary array and print its length as the required answer.
Illustration:
firstArr[] = {3, 5, 1, 8}
secondArr={3, 3, 4, 5, 3, 8}
Mapping: 3->0, 5->1, 1->2, 8->3 (From firstArr)
tempArr[] = {0, 0, 1, 0, 3}
Therefore, length of LIS of tempArr[] = 3 ({0, 1, 3})
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the Longest Common// Subsequence between the two arraysint LCS(vector<int>& firstArr, vector<int>& secondArr){ // Maps elements of firstArr[] // to their respective indices unordered_map<int, int> mp; // Traverse the array firstArr[] for (int i = 0; i < firstArr.size(); i++) { mp[firstArr[i]] = i + 1; } // Stores the indices of common elements // between firstArr[] and secondArr[] vector<int> tempArr; // Traverse the array secondArr[] for (int i = 0; i < secondArr.size(); i++) { // If current element exists in the Map if (mp.find(secondArr[i]) != mp.end()) { tempArr.push_back(mp[secondArr[i]]); } } // Stores lIS from tempArr[] vector<int> tail; tail.push_back(tempArr[0]); for (int i = 1; i < tempArr.size(); i++) { if (tempArr[i] > tail.back()) tail.push_back(tempArr[i]); else if (tempArr[i] < tail[0]) tail[0] = tempArr[i]; else { auto it = lower_bound(tail.begin(), tail.end(), tempArr[i]); *it = tempArr[i]; } } return (int)tail.size();}// Driver Codeint main(){ vector<int> firstArr = { 3, 5, 1, 8 }; vector<int> secondArr = { 3, 3, 5, 3, 8 }; cout << LCS(firstArr, secondArr); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Function to find the Longest Common// Subsequence between the two arraysstatic int LCS(int[] firstArr,int[] secondArr){ // Maps elements of firstArr[] // to their respective indices HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); // Traverse the array firstArr[] for (int i = 0; i < firstArr.length; i++) { mp.put(firstArr[i], i + 1); } // Stores the indices of common elements // between firstArr[] and secondArr[] Vector<Integer> tempArr = new Vector<>(); // Traverse the array secondArr[] for (int i = 0; i < secondArr.length; i++) { // If current element exists in the Map if (mp.containsKey(secondArr[i])) { tempArr.add(mp.get(secondArr[i])); } } // Stores lIS from tempArr[] Vector<Integer> tail = new Vector<>(); tail.add(tempArr.get(0)); for (int i = 1; i < tempArr.size(); i++) { if (tempArr.get(i) > tail.lastElement()) tail.add(tempArr.get(i)); else if (tempArr.get(i) < tail.get(0)) tail.add(0, tempArr.get(i)); } return (int)tail.size();}// Driver Codepublic static void main(String[] args){ int[] firstArr = { 3, 5, 1, 8 }; int[] secondArr = { 3, 3, 5, 3, 8 }; System.out.print(LCS(firstArr, secondArr));}}// This code is contributed by gauravrajput1 |
Python3
# Python3 program to implement# the above approachfrom bisect import bisect_left# Function to find the Longest Common# Subsequence between the two arraysdef LCS(firstArr, secondArr): # Maps elements of firstArr[] # to their respective indices mp = {} # Traverse the array firstArr[] for i in range(len(firstArr)): mp[firstArr[i]] = i + 1 # Stores the indices of common elements # between firstArr[] and secondArr[] tempArr = [] # Traverse the array secondArr[] for i in range(len(secondArr)): # If current element exists in the Map if (secondArr[i] in mp): tempArr.append(mp[secondArr[i]]) # Stores lIS from tempArr[] tail = [] tail.append(tempArr[0]) for i in range(1, len(tempArr)): if (tempArr[i] > tail[-1]): tail.append(tempArr[i]) elif (tempArr[i] < tail[0]): tail[0] = tempArr[i] else : it = bisect_left(tail, tempArr[i]) it = tempArr[i] return len(tail) # Driver Codeif __name__ == '__main__': firstArr = [3, 5, 1, 8 ] secondArr = [3, 3, 5, 3, 8 ] print (LCS(firstArr, secondArr))# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;public class GFG{// Function to find the longest Common// Subsequence between the two arraysstatic int LCS(int[] firstArr,int[] secondArr){ // Maps elements of firstArr[] // to their respective indices Dictionary<int,int> mp = new Dictionary<int,int>(); // Traverse the array firstArr[] for (int i = 0; i < firstArr.Length; i++) { mp.Add(firstArr[i], i + 1); } // Stores the indices of common elements // between firstArr[] and secondArr[] List<int> tempArr = new List<int>(); // Traverse the array secondArr[] for (int i = 0; i < secondArr.Length; i++) { // If current element exists in the Map if (mp.ContainsKey(secondArr[i])) { tempArr.Add(mp[secondArr[i]]); } } // Stores lIS from tempArr[] List<int> tail = new List<int>(); tail.Add(tempArr[0]); for (int i = 1; i < tempArr.Count; i++) { if (tempArr[i] > tail[tail.Count-1]) tail.Add(tempArr[i]); else if (tempArr[i] < tail[0]) tail.Insert(0, tempArr[i]); } return (int)tail.Count;}// Driver Codepublic static void Main(String[] args){ int[] firstArr = { 3, 5, 1, 8 }; int[] secondArr = { 3, 3, 5, 3, 8 }; Console.Write(LCS(firstArr, secondArr));}}// This code is contributed by Rajput-Ji. |
Javascript
<script>// Javascript program to implement// the above approach// Function to find the longest Common// Subsequence between the two arraysfunction LCS(firstArr, secondArr){ // Maps elements of firstArr[] // to their respective indices let mp = new Map() // Traverse the array firstArr[] for(let i = 0; i < firstArr.length; i++) { mp.set(firstArr[i], i + 1); } // Stores the indices of common elements // between firstArr[] and secondArr[] let tempArr = []; // Traverse the array secondArr[] for(let i = 0; i < secondArr.length; i++) { // If current element exists in the Map if (mp.has(secondArr[i])) { tempArr.push(mp.get(secondArr[i])); } } // Stores lIS from tempArr[] let tail = []; tail.push(tempArr[0]); for(let i = 1; i < tempArr.length; i++) { if (tempArr[i] > tail[tail.length - 1]) tail.push(tempArr[i]); else if (tempArr[i] < tail[0]) tail.unshift(0, tempArr[i]); } return tail.length;}// Driver Codelet firstArr = [ 3, 5, 1, 8 ];let secondArr = [ 3, 3, 5, 3, 8 ];document.write(LCS(firstArr, secondArr));// This code is contributed by gfgking</script> |
Output:
3
Time Complexity: O(NlogN)
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!
