Longest Increasing Subsequence: O(n log n) Deep Dive with DP

The Longest Increasing Subsequence (LIS) problem shows up everywhere you need to measure 'how ordered can this data get?' — from DNA sequence alignment in bioinformatics, to version-conflict resolution in distributed systems, to patience sorting algorithms used in real card games. It's deceptively simple to describe but hides serious algorithmic depth. Companies like Google, Meta, and Jane Street use it as a litmus test for whether a candidate truly understands dynamic programming versus just memorising patterns.

The core challenge: given an unsorted array of numbers, find the length (and elements) of the longest subsequence where every element is strictly greater than the previous one. The tricky part is 'subsequence' — you don't need contiguous elements. You can skip as many elements as you like, as long as the ones you pick stay in their original left-to-right order and keep going up. A brute-force check of all 2^n subsets is obviously off the table for anything real-world sized.

By the end of this article you'll understand not one but two fundamentally different approaches — the classic O(n²) DP table and the elegant O(n log n) patience-sort algorithm — know how to reconstruct the actual subsequence (not just its length), handle tricky edge cases like duplicates and negative numbers, and walk into an interview ready to explain the why behind every decision, not just recite the code.

What is Longest Increasing Subsequence (LIS)? — Plain English

The Longest Increasing Subsequence (LIS) problem: given an array of numbers, find the length of the longest subsequence where each element is strictly greater than the previous. Elements do not need to be contiguous.

Example: in [3, 1, 8, 2, 5], the LIS is [1, 2, 5] with length 3 (or [3, 8] is length 2, [1, 5] is length 2).

Real-world uses: scheduling problems where tasks must follow a precedence order, finding the maximum number of non-overlapping intervals that can be stacked, and as a building block for the patience sorting algorithm.

How Longest Increasing Subsequence (LIS) Works — Step by Step

O(n^2) DP approach: 1. Define dp[i] = length of the LIS ending at index i. 2. Initialize all dp[i] = 1 (each element is an LIS of length 1 by itself). 3. For each i from 0 to n-1: For each j from 0 to i-1: If arr[j] < arr[i]: dp[i] = max(dp[i], dp[j] + 1) 4. Return max(dp).

O(n log n) Binary Search approach (patience sorting): 1. Maintain a 'tails' array where tails[i] = the smallest tail element of all increasing subsequences of length i+1. 2. For each number x in the array: - Binary search for the leftmost position in tails where tails[pos] >= x. - If no such position: append x to tails (extends the longest subsequence). - Else: replace tails[pos] with x (allows a better (smaller tail) subsequence of that length). 3. Return len(tails).

Worked Example — Tracing the Algorithm

Array: [3, 1, 8, 2, 5, 4, 6]. Find LIS.

O(n^2) DP trace: dp = [1, 1, 1, 1, 1, 1, 1] (start) i=0 (3): no j before. dp[0]=1. i=1 (1): j=0: arr[0]=3 > 1. No update. dp[1]=1. i=2 (8): j=0: 3<8, dp[2]=max(1,dp[0]+1)=2. j=1: 1<8, dp[2]=max(2,dp[1]+1)=2. dp[2]=2. i=3 (2): j=0: 3>2. j=1: 1<2, dp[3]=max(1,dp[1]+1)=2. j=2: 8>2. dp[3]=2. i=4 (5): j=0: 3<5, dp[4]=max(1,2)=2. j=1: 1<5, dp[4]=max(2,2)=2. j=2: 8>5. j=3: 2<5, dp[4]=max(2,3)=3. dp[4]=3. i=5 (4): j=3: 2<4, dp[5]=max(1,3)=3. dp[5]=3. i=6 (6): j=0: 3<6->2. j=3: 2<6->3. j=4: 5<6->4. j=5: 4<6->4. dp[6]=4. dp = [1, 1, 2, 2, 3, 3, 4]. max=4.

O(n log n) patience sort trace: x=3: tails=[3] x=1: 1 replaces 3. tails=[1] x=8: 8 > all. tails=[1,8] x=2: 2 replaces 8. tails=[1,2] x=5: 5 > all. tails=[1,2,5] x=4: 4 replaces 5. tails=[1,2,4] x=6: 6 > all. tails=[1,2,4,6] len(tails)=4. LIS length = 4 (e.g., [1,2,5,6] or [1,2,4,6]).

Implementation

The following implementation demonstrates Longest Increasing Subsequence (LIS) with clear comments.

import bisect

def lis_dp(arr):
    """O(n^2) DP approach"""
    n  = len(arr)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp) if dp else 0

def lis_binary(arr):
    """O(n log n) patience-sort approach"""
    tails = []
    for x in arr:
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

arr = [3, 1, 8, 2, 5, 4, 6]
print('O(n^2) LIS:', lis_dp(arr))     # 4
print('O(n log n) LIS:', lis_binary(arr))  # 4

Frequently Asked Questions