Longest Increasing Subsequence

Q: What is the time complexity of Longest Increasing Subsequence?

The tails method runs in O(n log n) time and O(n) space: one binary search per element. The dynamic programming table over every pair of indexes takes O(n²) time, and trying every subsequence takes O(2ⁿ) . For n = 2500 that is about 30,000, 3 million and an astronomical number of steps.

Q: Why does the patience sorting method give the right length?

After each element, tails[k] holds the smallest value that any increasing subsequence of length k+1 seen so far can end with. Appending happens only when x is larger than every tail, which means a subsequence one longer than any before it now exists. Replacing never changes the length, it only lowers an ending, so the list's length is always the length of the longest increasing subsequence.

Q: How do you get the actual longest increasing subsequence, not only its length?

Record a parent for every element. In the O(n²) table, the parent of i is the j that gave ending[i] its value. In the tails method, store the index of the element behind each tail, and set an element's parent to the index stored one position to its left when it is placed. Then walk the parents back from the end of the longest subsequence and reverse the result.

Q: How do you find the longest non-decreasing subsequence instead?

Allow equal neighbors. In the table, use nums[j] ≤ nums[i] . In the tails method, search for the first tail that is strictly greater than x instead of greater or equal, so an equal value extends the list rather than replacing a tail. [7, 7, 7, 7] then returns 4.

MediumDynamic programming Binary search

+10

You get a list of integers nums. A subsequence keeps some of the elements, in their original order, and drops the rest; the kept elements do not have to sit next to each other. Return the length of the longest subsequence whose values strictly increase from left to right. Two equal values in a row do not count as increasing.

Function

lengthOfLIS(nums: integer-array) → integer

numsinteger-array: the list of integers to pick from
Returnsinteger: the length of the longest strictly increasing subsequence

Constraints

1 ≤ nums.length ≤ 2500
-10⁴ ≤ nums[i] ≤ 10⁴

Examples

Input: nums = [3, 1, 8, 2, 5, 9, 4, 7]
Output: 4
Explanation: Keeping 1, 2, 5, 9 gives an increasing subsequence of length 4, and so do 1, 2, 5, 7 and 1, 2, 4, 7. No choice of five values keeps rising, so the answer is 4.

+20 hidden tests on Submit

Follow-up

Can you return one longest increasing subsequence itself, not only its length, and still run in O(n log n) time?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A subsequence may skip any element, so a list of n numbers has 2^n of them, far too many to check. The dynamic programming fix is to ask a narrower question for every index: how long is the best increasing subsequence that ends exactly here? That gives an O(n²) table. The fastest version keeps one number per length, the smallest value a subsequence of that length can end with, and places each new element with a binary search.

Take or skip every element

Correct, but does not finish on the largest tests

Intuition

Walk through the list and make one decision per element: keep it or leave it out. You may keep nums[i] only when it is larger than the last value you kept. A recursive function longest(i, prev) answers: if the last kept element sits at index prev (or -1 when nothing is kept yet), how many more elements can you add from index i on?

Skipping gives longest(i+1, prev). Keeping, when it is allowed, gives 1 + longest(i+1, i). The answer is the larger of the two, and past the end of the list nothing more can be added, so the result there is 0. Every increasing subsequence is one path of keep and skip choices, so the search cannot miss the best one.

It is slow because both branches stay open whenever the values rise. On a list like 1, 2, 3, ..., n the calls double with every element: 2 to the power 40 is already about 10^12 calls, and the large tests have 2500 elements. Yet longest(i, prev) depends only on the pair (i, prev), so there are at most n² different questions. Asking each one once is the next approach.

Algorithm

Write longest(i, prev), where prev is the index of the last kept element, or -1.
If i is past the end, return 0.
Skip nums[i]: best = longest(i+1, prev).
If prev is -1 or nums[i] > nums[prev], keep it: best = max(best, 1 + longest(i+1, i)).
Return best. The answer is longest(0, -1).

def lengthOfLIS(nums):
    def longest(i, prev):
        # The longest increasing subsequence of nums[i:] whose values all exceed nums[prev].
        # prev is -1 while nothing has been taken.
        if i == len(nums):
            return 0
        best = longest(i + 1, prev)  # skip nums[i]
        if prev == -1 or nums[i] > nums[prev]:
            best = max(best, 1 + longest(i + 1, i))  # take nums[i]
        return best

    return longest(0, -1)

Longest subsequence ending at each index

Intuition

State. Let ending[i] be the length of the longest increasing subsequence whose last element is nums[i]. Fixing the last element is what makes the problem split cleanly: once you know where a subsequence ends, you know which later values may follow it.

Recurrence. If the subsequence ending at nums[i] has more than one element, the one before nums[i] is some nums[j] with j < i and nums[j] < nums[i], and the part up to it should be as long as possible. So ending[i] = 1 + max(ending[j]) over those j. Base case: every element alone is a subsequence, so ending[i] starts at 1. Order: ending[i] reads only smaller indexes, so fill it from left to right.

For [3, 1, 8, 2, 5, 9, 4, 7] the table is [1, 1, 2, 2, 3, 4, 3, 4]. For example 5 can follow 3, 1 or 2, and the best of those is 2 with ending = 2, so ending[4] = 3. The answer is the largest entry, 4, not the last one: the best subsequence can end anywhere.

Each index looks at every earlier index once, so the work is n(n-1)/2 comparisons, about 3.1 × 10^6 for n = 2500.

Algorithm

Create ending with every entry set to 1.
For each i from left to right, look at every j < i.
If nums[j] < nums[i], set ending[i] to ending[j] + 1 when that is larger.
Return the largest value in ending.

def lengthOfLIS(nums):
    n = len(nums)
    # ending[i]: the longest increasing subsequence that ends with nums[i]
    ending = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i] and ending[j] + 1 > ending[i]:
                ending[i] = ending[j] + 1
    return max(ending)

Smallest tails with binary search

Intuition

The table above remembers one length per index. You can remember less: for every length, only the smallest value an increasing subsequence of that length can end with. Call it tails[k] for length k+1. A smaller ending is always at least as good, because any value that can follow a subsequence ending in 9 can also follow one ending in 5.

tails is always sorted in strictly increasing order: a subsequence of length k+2 ending at t contains one of length k+1 that ends below t. So for each new value x, binary search for the first tail that is ≥ x. If there is none, x is larger than every tail and extends the longest subsequence, so append it. Otherwise replace that tail with x: the subsequence one shorter ends below x, so adding x gives the same length with a smaller ending.

For [3, 1, 8, 2, 5, 9, 4, 7], tails goes [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7], and its length 4 is the answer. At the step [1, 2, 4, 9] the 4 came after the 9 in the input, so tails is not itself a subsequence; only its length means something. The method is also called patience sorting, after the card game where each tail is the top card of a pile.

Each element costs one binary search over at most n tails: about 2500 × 12 = 30,000 steps for the largest input.

Algorithm

Start with an empty list tails.
For each x in nums, binary search for the first index k with tails[k] ≥ x.
If no tail is ≥ x, append x.
Otherwise set tails[k] = x.
Return the length of tails.

from bisect import bisect_left


def lengthOfLIS(nums):
    # tails[k]: the smallest last value of any increasing subsequence of length k + 1
    tails = []
    for x in nums:
        k = bisect_left(tails, x)  # the first tail that is >= x
        if k == len(tails):
            tails.append(x)  # x extends the longest subsequence so far
        else:
            tails[k] = x  # x is a smaller ending for length k + 1
    return len(tails)

Pitfalls and edge cases

Most wrong answers come from mixing up what the table holds or from treating equal values as increasing.

Returning ending[n-1] instead of the largest entry. For [1, 2, 3, 0] the last entry is 1, but the answer is 3.
Comparing with ≤ instead of <. [7, 7, 7, 7] must return 1, not 4.
In the tails version, searching for the first tail > x instead of ≥ x. With duplicates that appends the second 7 after the first and counts equal values as a longer subsequence.
Treating tails as the subsequence itself. Its values can come from different subsequences, so print it only if you track parents separately.
Solving the contiguous version by mistake. In [3, 1, 8, 2, 5, 9, 4, 7] the longest rising run of neighbors is 2, 5, 9 (length 3), while the answer is 4.
In Lua and R, arrays start at 1, so a 0-based prev = -1 marker becomes 0 and the binary search runs over indexes 1 to the current size.

Frequently asked questions4

What is the time complexity of Longest Increasing Subsequence?

The tails method runs in O(n log n) time and O(n) space: one binary search per element. The dynamic programming table over every pair of indexes takes O(n²) time, and trying every subsequence takes O(2ⁿ). For n = 2500 that is about 30,000, 3 million and an astronomical number of steps.

Why does the patience sorting method give the right length?

After each element, tails[k] holds the smallest value that any increasing subsequence of length k+1 seen so far can end with. Appending happens only when x is larger than every tail, which means a subsequence one longer than any before it now exists. Replacing never changes the length, it only lowers an ending, so the list's length is always the length of the longest increasing subsequence.

How do you get the actual longest increasing subsequence, not only its length?

Record a parent for every element. In the O(n²) table, the parent of i is the j that gave ending[i] its value. In the tails method, store the index of the element behind each tail, and set an element's parent to the index stored one position to its left when it is placed. Then walk the parents back from the end of the longest subsequence and reverse the result.

How do you find the longest non-decreasing subsequence instead?

Allow equal neighbors. In the table, use nums[j] ≤ nums[i]. In the tails method, search for the first tail that is strictly greater than x instead of greater or equal, so an equal value extends the list rather than replacing a tail. [7, 7, 7, 7] then returns 4.

Python

def lengthOfLIS(nums):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

nums = [3, 1, 8, 2, 5, 9, 4, 7]

Expected

Longest Increasing Subsequence

Function

Constraints

Examples

Hints

Solution

Take or skip every element

Longest subsequence ending at each index

Smallest tails with binary search

Pitfalls and edge cases

Frequently asked questions4

Similar problems