Longest Increasing Subsequence

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence keeps the original left-to-right order but may drop any elements; it does not have to be contiguous.

Examples

nums = [10,9,2,5,3,7,101,18] → 4 — one longest increasing subsequence is [2,3,7,101] (also [2,3,7,18]).
nums = [0,1,0,3,2,3] → 4 — e.g. [0,1,2,3].
nums = [7,7,7,7] → 1 — “strictly” increasing, so equal elements don’t extend anything.

Constraints

1 <= nums.length <= 2500
-10⁴ <= nums[i] <= 10⁴
A follow-up asks for an O(n log n) solution.

Think about it first

Hint 1

Define dp[i] = length of the longest increasing subsequence that ends exactly at index i. What smaller answers does it build on? Look at every earlier index j with nums[j] < nums[i].

Hint 2

dp[i] = 1 + max(dp[j]) over all j < i with nums[j] < nums[i], or 1 if there's no such j. The answer is max(dp), not dp[n-1]. That's O(n²).

Hint 3

For O(n log n): keep 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 the first tail that is >= it and overwrite it (or append). The length of tails is the answer. This is patience sorting.

TL;DR

Patience-sorting with binary search — O(n log n) time, O(n) space. The classic O(n²) DP is the stepping stone.

Approach 1 — Brute-force recursion

At each element, choose to take it or skip it. Track the last value taken so a new element is only taken when it is strictly larger.

Recurrence: lis(i, prev) = max(skip: lis(i+1, prev), take: 1 + lis(i+1, nums[i]) if nums[i] > prev). Base: lis(n, prev) = 0.

def lengthOfLIS(nums: list[int]) -> int:
    n = len(nums)

    def rec(i: int, prev: float) -> int:
        if i == n:
            return 0
        best = rec(i + 1, prev)          # skip
        if nums[i] > prev:               # take
            best = max(best, 1 + rec(i + 1, nums[i]))
        return best

    return rec(0, float("-inf"))

Complexity: two branches per element → O(2ⁿ) time. Useful for reasoning about the recurrence, but impractical beyond about 20 elements.

Approach 2 — Memoized top-down

The insight: the only state that matters is the current index, so the number of distinct subproblems is bounded by n. Keying on the index (rather than the previous value) keeps the cache key discrete.

Recurrence: dp[i] = longest increasing subsequence starting at i and taking nums[i].

from functools import lru_cache

def lengthOfLIS(nums: list[int]) -> int:
    n = len(nums)

    @lru_cache(maxsize=None)
    def rec(i: int) -> int:
        best = 1
        for j in range(i + 1, n):
            if nums[j] > nums[i]:
                best = max(best, 1 + rec(j))
        return best

    return max(rec(i) for i in range(n))

Complexity: O(n) states, each scanning O(n) successors → O(n²) time, O(n) space.

Approach 3 — Tabulated bottom-up (O(n²))

The insight: dp[i] = length of the longest increasing subsequence ending at i. Fill left to right; every dp[i] looks back at all smaller earlier values.

def lengthOfLIS(nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

Walkthrough (nums = [10,9,2,5,3,7,101,18]): dp becomes [1,1,1,2,2,3,4,4]. Index 5 (value 7) sees 2,5,3 as smaller with best dp = 2, so dp[5] = 3; index 6 (value 101) sees all, best is dp[5] = 3, so dp[6] = 4. Answer max(dp) = 4.

Complexity: O(n²) time, O(n) space.

Approach 4 — Patience sorting with binary search (O(n log n))

The insight: maintain tails, where tails[k] is the smallest tail value achievable by an increasing subsequence of length k+1. tails is always sorted. For each x, find the leftmost tail >= x and replace it with x (keeping that length “cheaper”); if x exceeds every tail, append it (a longer subsequence is now possible). bisect_left does the search in O(log n). The final length of tails is the answer — though tails itself is not a valid subsequence, only its length is meaningful.

from bisect import bisect_left

def lengthOfLIS(nums: list[int]) -> int:
    tails: list[int] = []
    for x in nums:
        pos = bisect_left(tails, x)   # first tail >= x (strictly increasing)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

Walkthrough (nums = [10,9,2,5,3,7,101,18]): 10→[10]; 9 replaces →[9]; 2→[2]; 5 append →[2,5]; 3 replaces 5 →[2,3]; 7 append →[2,3,7]; 101 append →[2,3,7,101]; 18 replaces 101 →[2,3,7,18]. Length 4.

Complexity: O(n log n) time, O(n) space. Uses bisect_left so equal values overwrite rather than extend — exactly what “strictly increasing” needs.

Common pitfalls

Returning dp[n-1] instead of max(dp) — the longest subsequence rarely ends at the last element.
Using bisect_right in Approach 4: that would treat equal values as extending the sequence, solving the non-strict variant instead.
Thinking tails is the actual subsequence — it can be a mix of values from different positions; only its length is guaranteed correct.

Pattern takeaway

“Longest/optimal subsequence ending at i” is the workhorse 1-D DP framing, and it’s O(n²) by default. When each step is a search over a sorted set of best-so-far values, a binary-searched auxiliary array (patience sorting) upgrades O(n²) to O(n log n). Watch the strict-vs-non-strict boundary — it’s just bisect_left vs bisect_right.