LIS Pattern

LIS O(n log n)

Maintain an array of the smallest tail elements for increasing subsequences of each length. For each new number, binary search for its position. This is called patience sorting and gives the LIS length in O(n log n).

O(n log n)

O(n)

How It Works

The O(n log n) LIS algorithm, based on patience sorting, maintains an array tails where tails[k] is the smallest possible last element of any increasing subsequence of length k+1. For each incoming number, binary search finds the first tail that is greater than or equal to it and replaces it; if the number exceeds every tail, it extends the array by one. Keeping each tail as small as possible maximizes future extension opportunities, which is why the greedy replacement is safe.

The tails array is always sorted, so each of the n elements costs one O(log n) binary search — O(n log n) total. The array's length equals the LIS length, but the array's contents are generally not an actual LIS; recovering one requires storing predecessor links.

Step-by-Step Visualization

LIS with patience sorting (O(n log n))

tails[]

1/3

Code

Java

static int lengthOfLIS(int[] nums) {
  List<Integer> tails = new ArrayList<>();

  for (int num : nums) {
    int lo = 0, hi = tails.size();
    while (lo < hi) {
      int mid = (lo + hi) >> 1;
      if (tails.get(mid) < num) lo = mid + 1;
      else hi = mid;
    }
    if (lo == tails.size()) tails.add(num);
    else tails.set(lo, num);
  }
  return tails.size();
}

Tips & Gotchas

1Maintain tails array: tails[i] = smallest tail of LIS of length i+1

2Binary search for the position to place each new element

3Length of tails array = length of LIS

Practice Problems

1Longest Increasing Subsequence
2Russian Doll Envelopes
3Increasing Triplet Subsequence
4Find the Longest Valid Obstacle Course at Each Position

About the LIS Pattern Pattern

Find the longest subsequence where every element is larger than the previous. Classic DP: for each element, find the longest increasing subsequence ending there. Can be optimized from O(n²) to O(n log n) with binary search.

Key insight

The framework: 1) Define state (what changes between subproblems). 2) Write recurrence relation. 3) Identify base cases. 4) Decide iteration order. Most DP is either 1D, 2D, or interval-based.

Common Dynamic Programming Interview Problems

Climbing Stairs
Coin Change
Longest Common Subsequence
0/1 Knapsack
Edit Distance
House Robber
Longest Increasing Subsequence
Word Break

Frequently Asked Questions

Why is the tails array not the actual subsequence?

Replacements overwrite earlier tails with smaller values that may come after later elements in the original array, so the stored values can be out of order relative to the input. The length is correct, but reconstructing a real LIS needs parent pointers recorded at insertion time.

How does Russian Doll Envelopes reduce to LIS?

Sort envelopes by width ascending, and by height descending among equal widths, then run LIS on the heights. The descending tie-break prevents two same-width envelopes from chaining, since an envelope cannot nest in another of identical width.

Does the binary search use lower bound or upper bound?

For a strictly increasing subsequence, search for the first tail >= x (lower bound) so equal values replace rather than extend. For non-decreasing subsequences, use the first tail > x (upper bound) so duplicates can stack.