Close

Longest Increasing Subsequence problem

Given an array of numbers, we have to find the longest sub sequence of that array which is strictly increasing.For example in the following array [8 1 4 2 7 9 5] {8,9}{1,4,7,9}{1,2,7,9}{1,2,5}{1,2,7}{1,2,9} are some of the increasing sub-sequences. The second and third are the longest increasing sub sequences with length 4. Our job is…

Common elements between two sorted arrays

Given two sorted arrays, how do you efficiently find the common elements between those two?Method#1: Simple and Brute-force approachIterate through one array, and try to find the element in another array using linear search. If it is found, then print it. This approach takes O(n^2) time as for each element in the first array we…