MediumArrayBinary SearchDynamic Programming

Longest Increasing Subsequence

1 approach, code in every language

You are given an integer array. A subsequence is any sequence you can obtain by deleting zero or more elements without changing the relative order of the elements that remain.

Return the length of the longest subsequence whose values are strictly increasing from left to right.

Example 1

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

Output: 4

One longest strictly increasing subsequence is [2, 3, 7, 101], which has length 4. Other choices such as [2, 5, 7, 18] also reach length 4.

Example 2

Input: nums = [7, 7, 7, 7, 7]

Output: 1

Every value is equal, so no pair is strictly increasing. The best you can do is pick a single element for a length of 1.

Constraints

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4

Patience Sorting with Binary Search

Maintain the smallest possible tail for every subsequence length and binary-search where each value belongs.

Loading animation…

Intuition

The direct dynamic program sets dp[i] = 1 + max(dp[j]) over all earlier j with nums[j] < nums[i], which is correct but runs in O(n^2). We can do better by tracking only what matters: the smallest possible tail value for an increasing subsequence of each length. Keep an array tails where tails[k] is the smallest value that can end an increasing subsequence of length k + 1. For each new number, binary-search for the first tail that is greater than or equal to it; replacing that tail keeps future extension options as open as possible, while appending when the number exceeds every tail grows the best length. The tails array itself is always sorted, which is exactly what makes the binary search valid. The final answer is simply the length of tails, since that equals the length of the longest increasing subsequence we could build.

Algorithm walkthrough

1Start with an empty tails array that will stay sorted throughout the scan.
2For each number, binary-search tails for the leftmost position whose value is >= the current number.
3If that position is past the end of tails, the number extends the longest chain so far, so append it.
4Otherwise overwrite tails at that position, lowering the tail for that length without changing the count.
5Because tails stays sorted and minimal, each replacement preserves correctness for later numbers.
6After processing every number, the length of tails is the length of the longest strictly increasing subsequence.

Implementation

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []
        for num in nums:
            lo, hi = 0, len(tails)
            while lo < hi:
                mid = (lo + hi) // 2
                if tails[mid] < num:
                    lo = mid + 1
                else:
                    hi = mid
            if lo == len(tails):
                tails.append(num)
            else:
                tails[lo] = num
        return len(tails)

Time

O(n log n)

Space

O(n)

Each of the n numbers triggers one binary search over the tails array, which never exceeds length n. The simpler O(n^2) dp[i] = 1 + max(dp[j]) formulation uses the same O(n) space but is slower.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Longest Rising Anomaly Pick is our own problem on the technique behind Longest Increasing Subsequence: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free