Longest Increasing Sub sequence

This is a classical problem that I came across a couple of hours ago, it intrigued me as I always knew the solution to be a DP approach of an O(n^2) .

When you shift your prospective into asking a different question you would find that it can be solved in O(N Log N) time, which is amazing in itself.

Introduction:-

I'll skip right into my observation, as there are a lot of resources covering different ways to tackle this problem, and I'll talk about my observation and hopefully it will shift your perspective too.

Summary:-

Increasing sub sequence has a property that it's a sorted array within an unordered array. this gives us the option to maintain an array with the sorted property with O(log N) cost in inserting non-ordered elements

Problem background:-

Given an array find the a sub sequence that is in increasing order

ex:-

input = [5,9,4,10,2,4]

output = 3 Explanation:- length of sub sequence [5,9,10] = 3 which is longer than [2,4], [4,10], [9,10]

Discussing different intuitions and approaches:-

• The first that comes to mind is to generate all possible sub sequences in O(2^n) time and do a check on each generated sub set if it fulfills the requirements or not
• The second is to do a backtrack approach (DFS with a condition to end search), starting from an index of i which array cells can fulfill the requirements, in worst case scenarios it can reach to O(2^n)
• The Third is an optimization to the backtrack approach to save the states the algorithms has been to in an array which is known is memorization, the dp approach this would take an O(N^2) time with a space O(N)
• The Fourth approach is to maintain a sorted array that fulfills the requirements. this will take up to O(K) space where K is the length of the longest sub sequence and O(N log N) time

Discussing implementation:-

When thinking about sorting problem usually what it comes to mind, do I have to sort the array first or not, however, sorting the array forces you to lose the property that you're looking for.

So what if you maintain a sorted version of the original array that you can always change according to the requirements of the problem.

looping through the original array

• Check if the next element in the array can be added your sorted array
• if not swap it with the first element that is > original element that violates this property

Justification:-

when you swap you risk getting a wrong representation of the longest increasing sub sequence, however it's justifiable as it fulfill the requirement

Example:-

with an array of [11, 22, 9] would result in a sorted array of [9, 22] of length 2 which still maintains the length property

• finally print the length of the sorted array

Pseudo code

function lengthOfLIS_bsearch(originalArray):
    n = length of originalArray
    sortedReq = [originalArray[0]]

    for i = 1 to n - 1:
        if originalArray[i] > sortedReq[last element of sortedReq]:
            sortedReq.push(originalArray[i])
        else:
        //looking for lower bound
            low = binary search index of sortedReq where originalArray[i] can be inserted
            sortedReq[low] = originalArray[i]
        end 
    end for
    
    return length of sortedReq
end function        

Problems with this implementation:-

• one problem is that you're not guaranteed to have the array responsible for the longest increasing sub sequence

Resources

• Problem link in leetcode
• DP implementation
• Geeks for geeks implementation and their own version of explaination