Longest Increasing Subsequence: O(n log n) DP Solution with Examples

The Longest Increasing Subsequence (LIS) problem is a classic challenge in computer science and dynamic programming. It asks for the length of the longest subsequence in an array where the elements are strictly increasing, though not necessarily contiguous. The problem has applications in areas like pattern recognition, data compression, version control systems, and even bioinformatics.

In this article, we focus on the optimized O(n log n) Dynamic Programming approach, which is significantly faster and more suitable for large inputs compared to the naive O(n²) DP solution. We will break the solution down step by step, use visual diagrams for clarity, and provide a fully worked-out Python example.

Table of Contents

Understanding the Longest Increasing Subsequence Problem

Given an array of integers arr = [10, 9, 2, 5, 3, 7, 101, 18], the goal is to find the length of the longest subsequence that is strictly increasing.

For example:

Input: [10, 9, 2, 5, 3, 7, 101, 18]
Longest Increasing Subsequence: [2, 3, 7, 18] or [2, 5, 7, 101]
Length = 4

Why Not O(n²) DP?

The traditional DP solution checks, for each element, the LIS ending before it, using nested loops. This takes O(n²), which becomes impractical for large arrays (e.g., thousands of elements). Instead, we rely on a clever trick that maintains a patience sorting-like array and uses binary search to achieve O(n log n).

O(n log n) Approach Explained

The optimized LIS algorithm maintains an array sub where:

sub is not the LIS itself but is crucial to tracking the length.
It represents the smallest possible tail values for increasing subsequences of different lengths.

Algorithm steps:

Initialize an empty list sub.
Iterate through each element x in the input array.
Use binary search to find the index in sub where x can replace an element (the first element >= x).
If x is larger than all elements in sub, append it.
Otherwise, replace the found element with x.

The length of sub at the end is the length of the LIS.

Step-by-Step Example

Consider the array [10, 9, 2, 5, 3, 7, 101, 18]:

Step	Element	Action	sub
1	10	Append	[10]
2	9	Replace 10 with 9	[9]
3	2	Replace 9 with 2	[2]
4	5	Append	[2, 5]
5	3	Replace 5 with 3	[2, 3]
6	7	Append	[2, 3, 7]
7	101	Append	[2, 3, 7, 101]
8	18	Replace 101 with 18	[2, 3, 7, 18]

Final sub = [2, 3, 7, 18] → Length = 4.

Python Implementation


from bisect import bisect_left

def length_of_LIS(nums):
    sub = []
    for x in nums:
        idx = bisect_left(sub, x)  # binary search
        if idx == len(sub):
            sub.append(x)
        else:
            sub[idx] = x
    return len(sub)

# Example
arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(length_of_LIS(arr))  # Output: 4

Interactive Example

If you’d like to experiment, try running the function with different arrays:


print(length_of_LIS([0, 1, 0, 3, 2, 3]))  # 4
print(length_of_LIS([7, 7, 7, 7, 7]))      # 1
print(length_of_LIS([4, 10, 4, 3, 8, 9]))  # 3

Time and Space Complexity

Time Complexity: O(n log n). Each insertion/replace operation is O(log n) due to binary search, applied to n elements.
Space Complexity: O(n). The auxiliary array sub grows up to n in the worst case.

Conclusion

The Optimized DP solution for Longest Increasing Subsequence is an elegant demonstration of combining greedy ideas with binary search to achieve better time complexity. It bridges dynamic programming with algorithmic insights from sorting techniques and is widely used in solving sequence-related problems efficiently. When solving LIS-based interview or competitive programming tasks, always prefer this O(n log n) version over the O(n²) approach for larger datasets.