Longest Increasing Subsequence DSA Solution

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.

Input	Output	Why
`nums = [10,9,2,5,3,7,101,18]`	`4`	One longest increasing subsequence is [2,3,7,101].

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

Step	State	Result
10	tails = [10]	length 1
9	replace 10	tails = [9]
2,5,3,7	tails becomes [2,3,7]	length 3
101 then 18	[2,3,7,101] then [2,3,7,18]	answer = 4

Complexity

Measure	Value	Reason
Time	O(n log n)	Each number performs one binary search over tails.
Space	O(n)	The tails array can grow up to n.

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

Why replace a tail with a smaller value?

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

Is tails the final subsequence?

Not necessarily. It is a helper array for lengths.

What is the core pattern?

Binary-search DP with greedy tails.

Longest Increasing Subsequence: Binary Search DP Pattern