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 table over every pair of indexes takes O(n²) time, and trying every subsequence takes O(2ⁿ) .

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 strictly greater than x , so an equal value extends the list instead of 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: 1, 2, 5, 9 rises, and so do 1, 2, 5, 7 and 1, 2, 4, 7: length 4. No choice of five values keeps rising.

Follow-up

Can you return one longest increasing subsequence itself, along with 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 list of n numbers has 2^n subsequences, far too many to check. Asking, for every index, how long the best increasing subsequence ending exactly there is gives an O(n²) table. The fastest version keeps, for each length, the smallest value a subsequence of that length can end with, and places each element with a binary search.

Take or skip every element

Correct, but does not finish on the largest tests

Intuition

Decide for each element whether to keep it; you may keep nums[i] only when it is larger than the last kept value. longest(i, prev) is the most elements you can still add from index i on, when the last kept element sits at prev (or -1). Skipping gives longest(i+1, prev); keeping gives 1 + longest(i+1, i). Every increasing subsequence is one path of these choices.

On 1, 2, 3, ..., n both branches stay open and the calls double with every element: 2^40 is already about 10^12. Yet there are at most n² different pairs (i, prev).

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

Let ending[i] be the length of the longest increasing subsequence whose last element is nums[i]. The element before nums[i], if any, 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, or 1 when there is none. 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]: 5 can follow 3, 1 or 2, and the best of those has length 2, so ending[4] = 3. The answer is the largest entry, since the best subsequence can end anywhere.

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

For every length, keep only the smallest value an increasing subsequence of that length can end with: tails[k] for length k+1. A smaller ending is never worse: anything that can follow a 9 can follow a 5. tails stays strictly increasing: drop the last value of an increasing subsequence of length k+2 and you get one of length k+1 that ends lower.

For each x, binary search for the first tail ≥ x. If there is none, append x: it extends the longest one. Otherwise replace that tail with x: the subsequence one shorter ends below x, so x gives the same length with a smaller ending.

For example 1, tails goes [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7]: length 4. In [1, 2, 4, 9] the 4 came after the 9, so only the length of tails means something.

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

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. The second 7 is then appended after the first, counting equal values as increasing.
Solving the contiguous version by mistake. In example 1 the longest rising run of neighbors is 2, 5, 9 (length 3), while the answer is 4.
Keeping 0-based indexes in Lua or R, where arrays start at 1. The prev = -1 marker becomes 0, and the binary search runs over indexes 1 to the current size.

Frequently asked questions3

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 table over every pair of indexes takes O(n²) time, and trying every subsequence takes O(2ⁿ).

What is patience sorting in Longest Increasing Subsequence?

It is the tails method named after a card game. Each tail is the top card of a pile: a card goes on the leftmost pile whose top is at least its value, or starts a new pile. The number of piles is the answer.

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 strictly greater than x, so an equal value extends the list instead of replacing a tail. [7, 7, 7, 7] then returns 4.

def lengthOfLIS(nums):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

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 questions3

Similar problems