Longest Increasing Subsequence

Given an integer array, return the length of the longest strictly increasing subsequence. A subsequence keeps the original order but may skip elements; it does not need to be contiguous.

Example#

For nums = [10, 9, 2, 5, 3, 7, 101, 18] one longest increasing subsequence is [2, 3, 7, 18] (or [2, 3, 7, 101]), so the answer is 4. For nums = [0, 1, 0, 3, 2, 3] the answer is 4.

Brute force note#

Generating every subsequence and checking which are increasing is exponential. A common O(n squared) DP sets length[i] to the best subsequence ending at i by scanning all earlier smaller elements, but we can do better.

Optimal approach#

Maintain a list “tails” where tails[k] is the smallest possible tail value of an increasing subsequence of length k+1. For each number, binary search for the leftmost tail that is greater than or equal to it. If found, overwrite it (a better, smaller tail for that length); if not, append (the number extends the longest run). The length of tails is the answer. The list is not an actual subsequence, but its length is correct.

 1from bisect import bisect_left
 2
 3
 4def length_of_lis(nums):
 5    tails = []
 6    for x in nums:
 7        i = bisect_left(tails, x)
 8        if i == len(tails):
 9            tails.append(x)
10        else:
11            tails[i] = x
12    return len(tails)
13
14
15print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 4
16print(length_of_lis([0, 1, 0, 3, 2, 3]))            # 4
17print(length_of_lis([7, 7, 7, 7]))                  # 1

Complexity#

Time is O(n log n): one pass with a binary search per element. Space is O(n) for the tails list. Using bisect_left enforces strictly increasing (duplicates replace rather than extend).

This blends DP thinking with binary search. Review the DP foundations on the dynamic programming topic page, then continue through the 60-day curriculum.