Longest Increasing Subsequence

Define dp[i] as the length of the longest increasing subsequence that ends exactly at index i. Any such subsequence either is just nums[i] alone (length 1), or extends some earlier increasing subsequence ending at a smaller value: for every j < i with nums[j] < nums[i], dp[i] could be dp[j] + 1. Taking the best such extension gives the recurrence, and the overall answer is the max over all dp[i].

Brute Force Recursion

Time O(2ⁿ)Space O(n)

Define lengthEndingAt(i) recursively: it is 1 plus the best lengthEndingAt(j) over all valid earlier indices j < i with nums[j] < nums[i], or just 1 if there is no such j.

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
        def lengthEndingAt(i: int) -> int:
            best = 1
            for j in range(i):
                if nums[j] < nums[i]:
                    best = max(best, 1 + lengthEndingAt(j))
            return best
        return max(lengthEndingAt(i) for i in range(n))

Each call can recurse into up to i earlier calls, and those overlap heavily across different starting indices, giving exponential O(2ⁿ) time in the worst case, O(n) recursion depth.

Bottom-Up DP

Time O(n²)Space O(n)

Fill dp[0..n-1] left to right, each starting at 1 (the subsequence containing just nums[i]), then scanning every earlier index j for a smaller value to extend.

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)

Trace for nums = [10, 9, 2, 5, 3, 7, 101, 18] (only the winning predecessor is shown as a pointer where one exists):

1 / 8

comparingresult

dp[0] = 1: "10" alone. No earlier elements to extend from.

For each of the n indices, up to n earlier indices are checked → O(n²) time, O(n) space for the dp array.

Patience Sorting (Binary Search)

OptimalTime O(n log n)Space O(n)

Maintain an auxiliary array tails, where tails[k] is the smallest possible tail value of any increasing subsequence of length k + 1 seen so far. For each new number, binary search tails for the first entry >= num: if found, replace it (a smaller tail keeps future extensions easier); if not found, num extends the longest subsequence so far, so append it. The final length of tails is the answer – note tails itself does not necessarily hold an actual valid subsequence, only correct lengths.

from bisect import bisect_left

class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        tails = []
        for num in nums:
            idx = bisect_left(tails, num)
            if idx == len(tails):
                tails.append(num)
            else:
                tails[idx] = num
        return len(tails)

Walking through nums = [10, 9, 2, 5, 3, 7, 101, 18]: tails evolves as [10] → [9] (10 replaced, since 9 is a smaller tail for length-1) → [2] → [2,5] → [2,3] (5 replaced by 3, a smaller tail for length-2) → [2,3,7] → [2,3,7,101] → [2,3,7,18] (101 replaced by 18). Final length is 4, matching the expected answer, even though [2,3,7,18] itself is not the actual LIS found earlier.

Each of the n numbers does one binary search (and possibly one write) over an array of size at most n → O(n log n) time, O(n) space for tails. This meets the problem’s follow-up requirement and is the best known complexity for this problem.