Longest Increasing Subsequence

Solving tips

Baseline O(n^2) DP: dp[i] = longest increasing subsequence ending at i = 1 + max(dp[j]) over j<i with nums[j]<nums[i]; answer is max(dp), not dp[n-1].
For O(n log n) use patience sorting: keep tails[k] = smallest tail of an increasing subsequence of length k+1; bisect and overwrite or append.
Use bisect_left for strictly increasing (equal values overwrite); bisect_right would solve the non-strict variant.
Remember tails is not an actual subsequence - only its final length is the answer.

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 decide take it or skip it, remembering the last value taken so we only take something 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.

class Solution:
    def lengthOfLIS(self, 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. Fine to explain, useless past ~20 elements.

Approach 2 — Memoized top-down

The insight: the state that matters is (i, index of the previous taken element) — finitely many pairs. Use the previous index rather than value so the cache key stays discrete.

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

from functools import lru_cache

class Solution:
    def lengthOfLIS(self, 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.

class Solution:
    def lengthOfLIS(self, 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

class Solution:
    def lengthOfLIS(self, 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.