Longest Increasing Subsequence in nlogn time

Find the longest increasing subsequence in nlogn time.

[serhiypidkuyko]

Hi Tushar
Thank you for your video
Some thoughts about the method.
1.You don't need the variable Len
2.The start size of the array T must be 1, in fact T=[0]
3.Every next step changes some of the elements of T or increases its size by 1
4.The final size of the array T is equal to the longest increasing subsequence size
5.(for some of your viewers) The main idea of this method is - to minimize the array T on every next step
The minimising means the following:T1<T2 if input(T1)<input(T2)
Here is the code in python:
#
def ceiling_in_assending_sorted_sublist_(v, li, t):
def helper(l, r):
if li[t[l]]>=v:
return l
elif li[t[r]]<v:
return r+1
elif l>=r-1:
return r
else:
m=(l+r)//2
if li[t[m]]<=v:
return helper(m, r)
else:
return helper(l, m)

if not li:
print('empty')
return
else:
return helper(0, len(t)-1)
#
def longest_inc_subseq_nlogn(li):
if not li:
print('empty')
return
n=len(li)
t=[0]
b=[-1]*n
for i in range(1, n):
v=li[i]
j=ceiling_in_assending_sorted_sublist_(v, li, t)
if j<len(t):
t[j]=i
if j>0:
b[i]=t[j-1]
else:
if t:
b[i]=t[-1]
t.append(i)

print('the longest increasing subsequence has {} elements'.format(len(t)))
j=t[-1]
indices=[]
result=[]
indices.append(j)
result.append(li[j])
while b[j]>-1:
j=b[j]
 indices.insert(0, j)
result.insert(0, li[j])

return indices, result
#
def test():
li=[3, 4, -1, 5, 8, 2, 3, 12, 7, 9, 10]
print(li)
indices, result=longest_inc_subseq_nlogn(li)
print(indices)
print(result)

[nsami]

Though I think the question "why the hell this works" remains unanswered in the video, but the tutorial helped me to get an idea about it. I want to share with you my thought. What we are doing in the array T is recording the last index of LIS of length 1 (at T[0]), LIS of length 2 (at T[1]) and so on. Whenever we encounter a new value (by new value I mean the current index of our array that we are processing) we search for the "LOWER BOUND" (for non-decreasing subsequence it should be "UPPER BOUND", I will explain it later) from the array obtained from the values at indexes saved in T. And then we change the corresponding index to our current index. Why do we do this? Consider this example, -1 2 3 12. This is our LIS of length 4. Now if we find 7, it is always better to save the array as -1 2 3 7. If you think greedily you will see why. Suppose your array has 9, 10, 11 yet to be discovered. If you did not change the 12 to 7 then you will never get the longest LIS because 9, 10, 11 are less than 12. At each step we update T greedily and whenever we find a longer LIS than we already have, we add the current index (the ending point of our newly found longest LIS) to the end of T.
Now can you see why we need UPPER BOUND for non-decreasing subsequences? If not let me know, I will explain in the comments. And also let me know if I am mistaken at somewhere, I wrote this based on my intuition.

[nderezic]

It would be nice if you could also explain the principle behind the algorithm you are using.

[sadmanahmmed]

I always love your explanation and find it easy. I dont know this time its seems hard to me

[kangin]

For those who can't find array R necessary, it's needed to find the actual LIS on top of its length because smaller numbers that come after in the original array can appear before in T. To see this clearly, array 3 4 -1 5 8 2 of size 6 gives -1 2 5 8 as its final T, but the actual sequence is 3 4 5 8. If you do not care about the actual LIS it's not needed :) Hope this helps!!

[xFurioCopter]

I really appreciate your work, helped me a lot to understand the Algorithm.
Thank you

[jackerjilly]

why we need R: if you look @5:00 and take {3, 4, -1, 5} as a shorten version of the problem the T array is {2, 1, 3}. For the answer to be a 'sequence' the entries if T must be strictly increasing. From T we map to the original array to get {-1, 4, 5}. From R we get {3, 4, 8}

[suruti]

This is really cool. It tries to keep track of subsequences that are possible at any point in time. Note that not all lengths are possible. Also for a given subsequence of length l, it only remembers the last sequence in the result array. Binary search replaces them with newer numbers later in the array which which makes it only remember the later sequences. Try a few examples and you see how the algorithm works. I had to watch it a few times before understanding what’s going on. Thanks Thushar for taking time to do this !

[reyaanuppal]

Sir, Whenever you say "Hello Friends, My name is Tushar" . I feel so awesome realizing that i am going to learn a new skill .😊. Thank you sir for helping the community.

[NITIN]

I really appreciate the way you explained. Thank you so much for your effort.

[MegaMam]

You are just awesome man... Referring your videos for almost all the dyn programming questions. Quite a cleaner way of problem solving.

[bhavyashah]

Your videos are genuinely very helpful! Thanks for doing this!

[Madeinchinaagain]

Great play-by-play explanation of a complicated dynamic programming problem.

[arafatkatze]

Brilliant work Tushar, I realized that i could actually understand the material by myself but it is always much better to understand an algorithm from your videos and the Correctness becomes very clear too, without the use of rigrous mathematics.
Thanks a lot, I appreciate the effort you put into this.

[nickthomas]

Using a binary search tree means that every time you insert a new element into the LIS it takes O(logn) time; and since you evaluate each of the n elements, your algorithm takes O(nlogn) time. Brilliant!

[AmitSingh-joob]

I think it can be solved in O(n) time complexity.
1. Find closest smaller element in left subarray. It can be done in O(n) using stack.
2. Just traverse from left to right and use following update rule:
2.a. If no smaller element in left subarray. Then output[.]=1
2.b. otherwise, output[i] = output[smaller_left]+1

[sohamchakravarty]

Fantastic and brilliant explanation Tushar. You make complex problems look so simple!! Thanks a lot!! :)

[sourabhkhandelwal]

Your videos are very helpful especially DP and Graphs. You have earned a fan. Kudos (y).

[ionutenache]

This is great! I really appreciate your work, helped me a lot to understand the algorithm. Thank you!

[dhruvsharma]

Thank you so much for the explanation. Watching this helped me a lot to further do it on my own. Again thanks for your effort.