Teaching Kids Programming – Greedy Algorithm to Find Longest Increasing Subsequence in O(NLogN) via Binary Search

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1

We have talked about finding the (length of the) Longest Increasing Subsequence using Dynamic Programming Algorithm and this takes O(N^2) quadratic time: Teaching Kids Programming – Longest Increasing Subsequence via Dynamic Programming Algorithm

Greedy Algorithm to Find Longest Increasing Subsequence in O(NLogN) via Binary Search

We keep the current best Longest Increase Subsequence when we iterate over the numbers. If the current number is bigger than all the numbers in the LIS, we just simply append it to the end. Otherwise, we find the insertion index (via bisect_left) and replace the number in the LIS with this one (smaller or equal). This works as we are greedily changing a number in LIS to a smaller or equal value which won’t make the result worse.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:        
        lis = []
        for n in nums:
            i = bisect_left(lis, n)
            if i == len(lis):
                lis.append(n)
            else:
                lis[i] = n
        return len(lis),

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:        
        lis = []
        for n in nums:
            i = bisect_left(lis, n)
            if i == len(lis):
                lis.append(n)
            else:
                lis[i] = n
        return len(lis),

The time complexity is O(NLogN) thus better than the Dynamic Programming Algorithm to find the Longest Increasing Subsequence.

Longest Increasing SubSequence

• Teaching Kids Programming – Longest Increasing Subsequence via Dynamic Programming Algorithm
• How to Find the Length of the Longest Increasing Subsequence using Dynamic Programming Algorithm?
• Teaching Kids Programming – Greedy Algorithm to Find Longest Increasing Subsequence in O(NLogN) via Binary Search

–EOF (The Ultimate Computing & Technology Blog) —