Longest Increasing Subsequence: Binary Search DP Pattern

Learning Outcome

After this lesson, you should be able to use tails to preserve future choices while computing LIS length in O(n log n).

Problem Statement

Given an integer array, return the length of the longest strictly increasing subsequence.

Brute Force Approach

For each index, compare with every previous index and build dp[i]. This is valid but costs O(n^2).

Optimized Approach

Maintain tails[len], the smallest possible ending value for an increasing subsequence of that length. Use binary search to replace the first tail >= current number.

Exact Pseudocode

tails = empty list
for x in nums:
  i = lower_bound(tails, x)
  if i equals length of tails:
    append x
  else:
    tails[i] = x
return length of tails
  

Reference Code

import bisect

class Solution:
    def lengthOfLIS(self, nums):
        tails = []
        for x in nums:
            i = bisect.bisect_left(tails, x)
            if i == len(tails):
                tails.append(x)
            else:
                tails[i] = x
        return len(tails)
  

Sample Dry Run

Complexity

Edge Cases

• Equal values do not extend a strictly increasing subsequence.
• An empty array returns 0.
• The tails array is not always the actual subsequence.

Interview Checklist

• Use lower_bound or bisect_left for strict increase.
• Return tails length, not the sum of tails.
• Do not treat replacement as deleting a real answer.

FAQs

A smaller tail gives future numbers more chance to extend the subsequence.

Not necessarily. It is a helper array for lengths.

Binary-search DP with greedy tails.