LeetCode 300 · 1-D DP

Longest Increasing Subsequence, explained with a picture

Dealing cards into patience piles.

Medium1-D DP
▶ Watch it step by step

The problem

Find the length of the longest strictly increasing subsequence: numbers picked from the list in order (not necessarily neighbours), each bigger than the last.

Input:  [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4   (e.g. 2, 3, 7, 18)

Picture it

Picture dealing cards into piles, left to right, like the game patience. A card goes onto the leftmost pile whose top card is ≥ it; if there is none, it starts a new pile on the right. The number of piles at the end equals the longest increasing run you could pick out. Finding the right pile is a binary search.

How to recognise it

  • You want the longest subsequence (items in order, gaps allowed) in which each value is strictly bigger than the one before.
  • The answer is a length, not the subsequence itself, so you may keep a summary instead of every candidate.
  • Up to 2,500 numbers rules out trying all subsets (2^2,500), and invites at least an O(n²) table.
  • For each length, only the smallest possible last value matters: a smaller tail leaves more room to extend. That observation allows a sorted summary and binary search, giving O(n log n).

Start with brute force

Try every subset of positions, keep those whose values strictly increase, and take the biggest size.

def lis_brute(nums):
    n = len(nums)
    best = 0
    for mask in range(1 << n):
        picked = [nums[i] for i in range(n) if mask >> i & 1]
        if all(a < b for a, b in zip(picked, picked[1:])):
            best = max(best, len(picked))
    return best

There are 2^n subsets, each checked in O(n), so time is O(n × 2^n). It is only usable for about 20 numbers; the limit is 2,500. Space is O(n) for a chosen list.

From brute force to the idea

  1. A first improvement (O(n²)). Let best[i] be the longest increasing subsequence ending at position i. For every earlier j with nums[j] < nums[i], best[i] = max(best[i], best[j] + 1). This is a correct table, but it compares every pair: about 3 × 10^6 pairs at n = 2,500.
  2. Keep only what matters. For each length k, store the smallest value that can end an increasing subsequence of length k. Call these piles; the shown code keeps only these tops.
  3. The tops are always sorted. Smaller lengths never need a bigger tail than longer ones, so piles is increasing. That means each new number x can be placed with binary search.
  4. Place each number. bisect_left(piles, x) finds the leftmost pile whose top is at least x. If no pile qualifies, x extends the longest run, so start a new pile. Otherwise x replaces that top: a smaller tail for the same length is never worse.
  5. Answer. The number of piles is the length of the longest increasing subsequence.

This is the key idea: keep, for each length, the smallest tail seen, and binary search where each new number belongs.

Note that piles is not itself a valid subsequence. For [4, 5, 1] it ends as [1, 5], whose order is not in the input; only its length (2) is meaningful.

The shown code imports it with from bisect import bisect_left.

The key idea

Patience sorting: keep pile tops (always sorted) and binary search where each card goes. O(n log n).

Python solution

def length_of_lis(nums):
    piles = []                       # top card of each pile, increasing
    for x in nums:
        i = bisect_left(piles, x)     # leftmost pile whose top is >= x
        if i == len(piles):
            piles.append(x)           # bigger than every top: new pile
        else:
            piles[i] = x              # place it on that pile
    return len(piles)

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from bisect import bisect_left

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n × 2^n): every subset is checkedO(n): the chosen values
Piles with binary search (shown code)O(n log n): n numbers, each found by an O(log n) binary searchO(n): the piles list in the worst case (a sorted input)

Edge cases

  • Empty list: returns 0.
  • One number ([5]): returns 1.
  • All equal ([7, 7, 7, 7]): returns 1, because bisect_left makes each 7 replace the top instead of starting a new pile (the problem wants strictly increasing).
  • Strictly decreasing ([3, 2, 1]): returns 1.
  • Already sorted ([1, 2, 3, 4]): returns 4.
  • Example [10, 9, 2, 5, 3, 7, 101, 18]: returns 4.
  • Duplicates in the middle ([4, 10, 4, 3, 8, 9]): returns 3 (3, 8, 9).

Common mistakes

  • Using bisect_right, which allows equal values: [7, 7, 7, 7] would give 4.
  • Appending every number to piles instead of replacing a top.
  • Returning the piles list as if it were the subsequence.
  • Forgetting the import, which causes a NameError for bisect_left.
Your turn: non-decreasing runs

Find the length of the longest non-decreasing subsequence (equal values are allowed). For [7, 7, 7, 7] the answer is 4, and for [4, 10, 4, 3, 8, 9] it is 4 (4, 4, 8, 9). Describe your approach, then write it if you like.

Compare with our answer

Equal values may now follow each other, so a new number should go after any pile top equal to it, which is bisect_right.

def lnds(nums):
    piles = []
    for x in nums:
        i = bisect_right(piles, x)
        if i == len(piles):
            piles.append(x)
        else:
            piles[i] = x
    return len(piles)

lnds([7, 7, 7, 7]) is 4 and lnds([3, 2, 1]) is 1. Time O(n log n), space O(n).

A strong answer mentions: that only the comparison changes (bisect_right for non-decreasing, bisect_left for strictly increasing), why the tops stay sorted, and the O(n log n) cost.

Check what stuck

1. You need the length of the longest strictly increasing subsequence of up to 100,000 numbers. Which approach fits best?

2. Why is the shown code O(n log n) rather than O(n²)?

3. A learner changes bisect_left to bisect_right. For which input is the answer now wrong?

Score 60% or more and the lesson is marked complete.