Skip to main content
Advanced

Longest Increasing Subsequence

mediumCore dynamic programmingGoogleMetaAmazon

Problem statement

You are given a list of integers nums. Return the length of the longest strictly increasing subsequence.

A subsequence keeps some of the values in their original order and drops the rest; the kept values don't have to be next to each other. "Strictly increasing" means each kept value is bigger than the one before it — equal values don't count.

For example, in [3, 1, 4, 2, 5] you can keep 1, 2, 5 or 3, 4, 5, so the answer is 3.

Examples

Example 1

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

Output: 4

Explanation: Keeping 2, 3, 7, 101 (or 2, 5, 7, 18) gives 4 values that rise each step. No choice of 5 values stays increasing.

Example 2

Input: nums = [0,1,0,3,2,3]

Output: 4

Explanation: 0, 1, 2, 3 uses the first 0, the 1, the 2 and the last 3, in that order. That is 4 values.

Example 3

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

Output: 1

Explanation: Every value is the same, and equal values don't count as increasing, so only one 7 can be kept.

Hints

Hint 1: For each position i, ask: what is the longest increasing subsequence that *ends* at nums[i]?

Approach

Optimal: Smallest tails + binary search

Intuition

Keep a list called tails. Entry k holds the smallest last value of any increasing subsequence of length k + 1 found so far. Why the smallest? A subsequence that ends lower is easier to extend later — 2, 3 is more useful than 2, 5, because more future values are bigger than 3 than bigger than 5.

tails is always sorted, which makes each update cheap. For a new value x:

  • If x is bigger than every entry, it extends the longest subsequence: append it.
  • Otherwise, find the first entry that is >= x and replace it with x. That keeps a subsequence of the same length but with a smaller ending.

The length of tails is the answer. Note that tails itself is usually not a real subsequence of nums — only its length is meaningful. Finding "the first entry >= x" is a binary search (look at the middle, keep the half that must contain it); using >= rather than > is what makes equal values not count as increasing.

Steps

  1. Start with an empty list tails.
  2. For each value x in nums:
    • Binary-search for the first position pos in tails with tails[pos] >= x.
    • If pos equals the length of tails, append x. Otherwise set tails[pos] = x.
  3. Return the length of tails.

Dry run

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

x first entry ≥ x action tails after
10 none append [10]
9 10 replace [9]
2 9 replace [2]
5 none append [2, 5]
3 5 replace [2, 3]
7 none append [2, 3, 7]
101 none append [2, 3, 7, 101]
18 101 replace [2, 3, 7, 18]

The list has length 4. Edge case: [7,7,7] — each 7 finds the existing 7 (>= 7) and replaces it, so tails stays [7] and the answer is 1.

Complexity

Time O(n log n) - We handle each of the n values once. For each one, a binary search in the `tails` list finds where it goes, which takes O(log n) steps because the list is sorted and never longer than n. For n = 2,500 that is about 2,500 × 12 = 30,000 steps instead of 3 million.

Space O(n) - The `tails` list grows by at most one entry per value, so it holds at most n numbers. Nothing else is stored.

from bisect import bisect_left
from typing import List


class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails: List[int] = []
        for x in nums:
            pos = bisect_left(tails, x)  # first index with tails[pos] >= x
            if pos == len(tails):
                tails.append(x)
            else:
                tails[pos] = x
        return len(tails)


if __name__ == "__main__":
    print(Solution().lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))  # 4
    print(Solution().lengthOfLIS([0, 1, 0, 3, 2, 3]))  # 4
    print(Solution().lengthOfLIS([7, 7, 7, 7, 7, 7, 7]))  # 1
RecapThe whole problem in a few lines, for the night before
  • Spot it: longest strictly increasing subsequence, where elements need not be next to each other
  • Idea: keep a tails list where tails[i] is the smallest possible last value of an increasing subsequence of length i + 1; for each number, binary search its position and replace it, or append if it is bigger than all; the answer is the list length
  • Cost: O(n log n) time, O(n) space (the simple DP is O(n²) time)
  • Trap: use the lower-bound position so equal values replace instead of extending, since the sequence must be strictly increasing; tails is not the actual subsequence

Interview follow-ups

  • Return one longest increasing subsequence, not just its length.

    With the O(n²) DP, also store prev[i]: the j that gave dp[i] its best value. Find the i with the largest dp[i], then follow prev back to the start and reverse the list. Time stays O(n²) and the extra array is O(n). The O(n log n) version can do it too with the predecessor trick from the FAQ.

  • Count how many longest increasing subsequences there are.

    Keep a second array count[i]: the number of longest subsequences ending at i. When dp[j] + 1 > dp[i], set dp[i] = dp[j] + 1 and count[i] = count[j]; when it's equal, add count[j] to count[i]. The answer is the sum of count[i] over all i with the largest dp[i]. This stays O(n²).

  • Values arrive one at a time and you must report the current answer after each one.

    The tails approach already works this way. Each new value does one binary search and one update, O(log n), and the current answer is just the length of tails. Memory is O(answer length), not O(n), because only tails is kept. The O(n²) DP would need to look back at every previous value for each new one.

Frequently asked questions

A subarray is a block of values that sit next to each other, like [2, 5, 3] inside [10, 9, 2, 5, 3, 7]. A subsequence may skip values but keeps their order, like [2, 3, 7]. This problem asks for a subsequence, which is why the answer can jump over values such as the 5.

Replacing an entry can mix values from different subsequences. For [3, 4, 1], tails ends as [1, 4], but 1 comes after 4 in the input, so [1, 4] isn't a real subsequence. The length is still right: there really is an increasing subsequence of length 2 (3, 4). Only the length is guaranteed.

Because the problem wants strictly increasing values. If x equals an entry, replacing that entry keeps the length the same, so equal values never make the list longer. Searching for the first value > x instead would append equal values and compute the longest non-decreasing subsequence — a different problem.

Yes, with a bit more bookkeeping. Store, for each position in tails, the index in nums of the value placed there, and for each value, the index of the value in the slot before it (its predecessor). At the end, start from the last slot and follow predecessors backward. Time stays O(n log n) and memory O(n).

It's a staple of software-engineering-heavy infra loops because it tests two things at once: turning a brute force into a DP, and then spotting a binary-search speed-up. The ordering idea also appears in real data, such as finding the longest run of monotonically increasing version numbers or sequence IDs in an out-of-order log.