LeetCode #300 Medium

Longest Increasing Subsequence

Length of the longest strictly increasing subsequence (elements keep order, need not be adjacent).

dpbinary-search

02

Intuition

💡

Classic DP: dp[i] = length of the best increasing subsequence ending at i, built by scanning all smaller earlier elements. The O(n log n) upgrade keeps a list tails where tails[k] is the smallest possible tail of an increasing subsequence of length k+1 — each new number either extends the list or improves (lowers) one tail via binary search.

03

Approach

1

O(n²) DP first

dp[i] = 1 + max(dp[j]) over all j < i with nums[j] < nums[i]. Answer is max(dp). Simple, and the base for many follow-up problems.

2

The tails insight

Among all increasing subsequences of length L, only the one with the smallest tail matters — it is the easiest to extend. So keep just that smallest tail per length: tails is sorted, enabling binary search.

3

Patience step

For each num: find the first tail ≥ num (bisect_left). If none, num extends the longest run (append). Otherwise it replaces that tail — same length, better (smaller) tail. Length of tails is the answer.

04

Solution & live demo

python

▶1from bisect import bisect_left
▶2 
▶3class Solution:
▶4    def lengthOfLIS(self, nums):
▶5        tails = []
▶6        for x in nums:
▶7            i = bisect_left(tails, x)
▶8            if i == len(tails):
▶9                tails.append(x)     # extends longest subsequence
▶10            else:
▶11                tails[i] = x        # same length, smaller tail
▶12        return len(tails)

05

Edge cases

Strictly decreasing input

Every number replaces tails[0]; answer 1.

Duplicates

bisect_left makes equal values replace, not extend — enforcing strict increase.

tails is not the LIS itself

Only its length is meaningful; elements may come from different subsequences.

06

Complexity

Time

O(n log n)

Space

O(n)

One binary search per element; O(n²) DP variant also accepted.