Longest Increasing Subsequence (LeetCode 300)

The problem

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence keeps the original order but may skip elements.

Input:  nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4

One longest choice is [2, 3, 7, 101]; [2, 5, 7, 18] also works. No increasing subsequence has 5 elements.

How to think about it

Start with brute force. Checking every subsequence is O(2ⁿ). The classic DP improves this: dp[i] = length of the longest increasing subsequence ending at i = 1 + the max dp[j] over earlier j with nums[j] < nums[i]. That is O(n²), fine for small inputs but slow at n = 10⁵, and interviewers often ask for better.

The key insight: for each length, only the smallest tail matters. Suppose two increasing subsequences have the same length, one ending in 5 and one ending in 3. The one ending in 3 is always at least as useful, because anything that can extend 5 can also extend 3. So keep an array tails, where tails[k] is the smallest possible last value of an increasing subsequence of length k + 1.

tails stays sorted, so binary search it. For each new x, find the first position whose tail is >= x (bisect_left). If there is none, x extends the longest subsequence, so append it. Otherwise x becomes a smaller tail for that length, so overwrite it. The length of tails at the end is the answer. (The array itself is not necessarily a real subsequence; only its length is meaningful.)

Which pattern is this? 1-D DP sped up with binary search. The tell is “longest increasing subsequence” with a large n: replace “best ending at i” with “best tail for each length”.

Approach

1. Start with an empty tails.
2. For each x in nums, find i = bisect_left(tails, x).
3. If i == len(tails), append x; otherwise set tails[i] = x.
4. Return len(tails).

Solution

import bisect
def length_of_lis(nums):
    tails = []                                    # tails[k] = smallest tail of an LIS of length k+1
    for x in nums:
        i = bisect.bisect_left(tails, x)          # first tail >= x
        if i == len(tails): tails.append(x)       # x extends the longest run
        else: tails[i] = x                        # x is a better (smaller) tail for length i+1
    return len(tails)
# length_of_lis([10,9,2,5,3,7,101,18]) -> 4  ([2,3,7,101])

Dry run

On [10, 9, 2, 5, 3, 7, 101, 18]:

len(tails) = 4.

Complexity

• Time: O(n log n). Each of the n elements does one binary search on an array of at most n items.
• Space: O(n). The tails array.

Edge cases and pitfalls

• Empty input returns 0; all equal ([7, 7, 7]) returns 1.
• Strict vs non-strict. bisect_left gives strictly increasing. Using bisect_right would allow equal values (longest non-decreasing).
• Reading tails as the answer subsequence is wrong; it can mix elements from different subsequences. Reconstruct with parent pointers if you need the actual sequence.
• Know the O(n²) DP too. It’s easier to derive under pressure and extends to variants like counting the number of LIS.

Related problems

• Maximum Subarray (LeetCode 53): the contiguous cousin with the same “best ending here” state.
• Longest Common Subsequence (LeetCode 1143): subsequences again, compared across two strings with a 2-D table.
• Search Insert Position (LeetCode 35): the bisect_left step on its own.