Longest Increasing Subsequence in O(nlogn)

Tags: , , , ,

In the last post, longest increasing subsequence, we discussed brute force and dynamic programming based solutions. The complexity of the brute force solution is exponential whereas for the dynamic programming approach it is O(n2). Question is – Can we find the longest increasing subsequence in O(nlogn) complexity?

Let’s revisit the problem statement: Given an array of integers, find the length of the longest increasing subsequence. An increasing subsequence contains elements A[i] and A[j] only if i < j and A[i]A[j].
For example,

Input:
[2,4,5,3,1,6,7], 
Output:
5
Explanation:
The increasing subsequences are [2,4,5,6,7], [2,3,6,7], [1,6,7] and many more. The longest subsequence here has a length of 5.

The basic idea behind the solution is to keep track of all active subsequences at a given point in time. Based on the current number being considered, update these active lists. To understand this process, let’s work out an example.

A = {2,8,7}
Monotonically increasing subsequences are {2,8} and {2,7}

What if we add another element, 11 in this?

A = {2,8,7,11}
Monotonically increasing subsequences are {2,8,11} and {2,7,11}

What if new element 9 is added to array? What happens now? If we add it t0 subsequences, the length of the longest subsequence remains 3.

A = {2,8,7,11,9}
Monotonically increasing subsequences are {2,8,9} and {2,7,9}

The decision to take for each element being considered is whether we create new active subsequences with length 3 with element 9 in them or continue with 11. If the next element is 10 we know that adding 9 to subsequence leads us to longer subsequences rather than keeping 11.

How do we decide when to replace and when to continue with the old element in the list of subsequences?
We add a new number A[i] to the sequence if A[i] > E, E is the last element in subsequence
and replace an number with A[i], if there exists a number A[j] such that if E > A[i] < A[j], it means, the new number falls somewhere between A[j] and E.

What if A[i] is smaller than all elements in the present list of subsequences? In this case, we have to create a new list and add A[i] into it. The invariant is to maintain lists of increasing sequences and update them based on the next number.
Each time a new element is to be added, scan all the lists of subsequences in decreasing order of their length. The following algorithm shows how to add/replace the new elements in the existing lists or to create a new list with it.

1. If A[i] is the smallest among all end candidates of active lists, start a new active list with A[i] of length 1.
2. If A[i] is largest among all end candidates of active lists, clone the largest active list, and append A[i] to it.
3. If A[i] is in between, find the list with the largest end number that is smaller than A[i]. Clone and append A[i] to this list.
4. Discard all other lists of the same length as that of this modified list.

LIS in nlogn example

Let’s take an example and see how it works with an array A = [ 0, 8, 4, 12, 2, 10, 6, 14].

For A[0], there are no active lists of subsequences, we will create a new one.
longest increasing subsequence in logn

Next, we go to A[1] which is 8. A[i] is greater than the ends of all the current lists, we will take the longest one and append A[1] to it.
longest increasing subsequence in logn

For A[2] with value 4, A[i] is less than the end of one of the list and greater than the end of other. We will find the list which has end less than A[i], in this case, the first list containing [0]. Clone it and append A[2] to it and discard all other lists of the same length.

For A[3] with value 12, it is the same case as A[1] since it is greater than all the ends of the current lists, we will clone the longest available list and append it to that.

A[4] with value 2, it has the same case as A[2], Clone the one with largest end which is less than A[4], append A[4] to it and discard all same length lists.

A[5] with value 10. Same as A[4]. Clone, extend, and discard all the same length subsequences.
Lists = [ [0], [0, 2], [0,2,10] ] and [0, 4, 12] is discarded.

A[6] is 6. Same as A[5] We will clone the list which has end smaller than A[6], extend it, and discard all other lists which have the same length.
Lists = [ [0], [0, 2], [0,2,6] ] and [0, 2, 10] is discarded.

Following the same approach, we will go through all the numbers in the given array. The longest increasing subsequence in the given array is [ 0,2,6,14] with a length of 4.
lis in nlogn

It seems like a lot of things need to be done just for maintaining the lists and there is significant space complexity required to store all of these lists. We can optimize on this, observe that we use only ends of the list and their sizes. We do not care what was prior to them in list. So, can we store the ends of all the lists of an auxiliary array and do operations on them? Size of this array in worst case will be n.

To append to the list, add another element in the auxiliary array. To replace just overwrite the smallest number which is greater than the current number. To find the smallest number which is greater than the current number, we can use binary search algorithm.

To find the length of the longest subsequence, keep track of the length of the auxiliary array because this will be the length of LIS.

Show me implementation of longest increasing subsequence in O(nlogn)

    public int lengthOfLIS(int[] nums) {
        
        if(nums == null || nums.length == 0) return 0;
        
        int [] dp = new int[nums.length]; 
        int len = 0;
        
        for(int num : nums){
            int index = Arrays.binarySearch(dp, 0, len, num);
            
            if(index < 0)
                index = -(index+1);
            dp[index] = num;
            
            if(index == len)
                len++;
        }
        
        return len;
    }

The complexity of this algorithm is O(nlogn) as for each element in the array, it requires O(logn) time to find the ceiling of it and put it at the correct position.

This article has taken some inspiration from: http://stackoverflow.com/questions/6129682/longest-increasing-subsequenceonlogn and the comments provided by readers under these articles.

What are the problems you can solve with the longest increasing subsequence?
1. Russian doll envelopes.
2. Box stacking problem.
3. Bridges across the river.

Please share if you find something wrong or missing. Also, if you want to contribute to the website, please refer to Publishing and contact us. We would love to publish your article and at the same time, will pay you too.