Longest Increasing Subsequence

Nitish Chandra
Aug 24, 2017 · 2 min read

In this post I will go through O(nlogn) solution for Longest Increasing Subsequence whose normal execution time is O(n2)

Problem description:

Given an unsorted array of integers, find the length of longest increasing subsequence.

Solution :

Lets take an array such as [10, 9, 2, 5, 3, 7, 101, 18]

The main issue with this problem is it is unsorted had it been sorted one could have just found out longest increasing subsequence by checking if an element at position x is greater than its predecessor element if that is true you just increase the longest increasing subsequence found at x — 1 by 1

So what can we do to facilitate this issue. Lets keep account of the smallest ending element of all sequence found thus so if we have two sequences of length 1 one ending with 3 and the other ending with 5 we would keep track of 3. Similarly we will keep track of sequences of length 2 , 3 and so on

Now here is an interesting observation The array thus maintained which we contain all the smallest ending element would be always sorted. This is because if an element is part of subsequence of length i and it is smaller than any of the last element of length i — 1, i -2 and so on . The new element would be the smallest ending element of subsequence i — 1 or i -2 and so on . So according to the definition it should always be sorted

Now once we have that array we seek to find the position(p) of new incoming element in the array such that array[p-1] ≤ element <array[p+1]

Once we have this we would append element to the p-1 position increasing its length by 1 and updating array[p+1] = element

if there is no such p + 1 that is element is greater than all the element it is added at the end

if the element is smaller than all the element array[0] == element

Since searching for p can be done 0(logn) the whole operation can be done in 0(nlongn) time

)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade