LIS Variants and Patience Sorting

Classic sequence DP gave the $O(n^2)$ longest increasing subsequence: dp[i] is the best run ending at i, and each i looks back at every predecessor. That is the version to explain. This page is the $O(n \log n)$ version — patience sorting — and the family of problems that reduce to it.

Two things make it worth a page of its own. First, the tails array it maintains is not a valid subsequence, and misunderstanding that is the standard error. Second, several problems that look nothing like LIS are LIS after a sort: Russian doll envelopes, minimum arrows to burst balloons, and the longest chain of pairs.

What you’ll learn

• What tails[k] actually means, and why the array is sorted for free.
• Why tails gives the right length but the wrong sequence.
• The one-character change between strictly increasing and non-decreasing.
• The sort-then-LIS reduction, and the tie-breaking detail that makes it correct.

The cue

You are looking at LIS when…

• The question asks for the longest subsequence (not substring) satisfying an ordering condition — increasing, non-decreasing, or a chain relation.
• Or it asks for the minimum number of groups into which a sequence can be split so each is decreasing — which is the same number, by Dilworth’s theorem.
• Or the input is a set of pairs and you need the longest chain where each dominates the previous in both coordinates.

The reduction to look for: sort by one coordinate, then run LIS on the other. That converts a two-dimensional ordering problem into a one-dimensional one, and it is the whole trick behind LC 354 and LC 646.

Reach for something else when the required run is contiguous — that is a sliding window or Kadane’s, both $O(n)$ — or when you need the longest common subsequence of two sequences, which is a different table.

Visual intuition

Start with the $O(n^2)$ version, because it is the one you explain first and the one whose answer is max(dp) rather than dp[-1]:

arrayThe O(n squared) version: every dp[i] looks back at every predecessor

Unknown ArrayStepper algo lis. Known keys: fixed-window, variable-window-sum, longest-unique, char-replacement, min-window, two-sum-sorted, reverse-in-place, dutch-flag, prefix-sums, kadane, cyclic-sort, remove-duplicates, container-water, trapping-rain, subarray-sum-k, bubble-sort, selection-sort, insertion-sort, merge-sort, quick-sort, binary-search, binary-search-lower-bound, binary-search-rotated, count-set-bits, xor-single, bitmask-subsets, anagram-window, expand-around-centre, sliding-window-max, kmp-prefix, jump-game, comparator-keys, sieve, lru-cache, swap-remove, timestamp-window, hash-chaining.

What tails actually holds

patience_sorting.py

from bisect import bisect_left, bisect_right
 
 
def lis_length(nums):                         # strictly increasing
    tails = []                                 # tails[k] = smallest possible tail
    for x in nums:                             #            of a run of length k+1
        i = bisect_left(tails, x)              # first tail >= x
        if i == len(tails):
            tails.append(x)                    # x extends the longest run
        else:
            tails[i] = x                       # x is a better tail for length i+1
    return len(tails)
 
 
def lnds_length(nums):                        # NON-decreasing: one change
    tails = []
    for x in nums:
        i = bisect_right(tails, x)            # bisect_right, not left
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)
 
 
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18]))   # expect 4
print(lnds_length([2, 2, 2]))                      # expect 3
print(lis_length([2, 2, 2]))                       # expect 1

tails[k] is the smallest value that can end an increasing run of length k + 1, given everything seen so far. Two consequences follow:

• tails is always sorted, which is what makes the binary search legal. It is sorted not by accident but because a longer run must end at a value at least as large as a shorter one’s best tail.
• Replacing tails[i] never shortens anything. A smaller tail for the same length is strictly better — it leaves more room for future values — and the lengths already achievable stay achievable.

tails is not a subsequence, and its length is the only trustworthy output

Run the algorithm on [10, 9, 2, 5, 3, 7, 101, 18] and tails ends as [2, 3, 7, 18]. That happens to be a valid increasing subsequence here — which is misleading, because it is not guaranteed.

On [1, 3, 5, 2], tails ends as [1, 2, 5]. But 1, 2, 5 is not a subsequence of the input: 2 appears after 5. The length 3 is correct (1, 3, 5), the contents are not.

tails mixes tails from different runs at different times. To recover an actual subsequence you need a parent-pointer array recording, for each element, the index it extended — then walk backwards from the last appended element. If a problem asks for the sequence rather than the length, say this explicitly; it is the most common follow-up.

Dry run

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

x	bisect_left(tails, x)	action	tails after
10	0 (empty)	append	[10]
9	0	replace tails[0]	[9]
2	0	replace tails[0]	[2]
5	1 = len	append	[2, 5]
3	1	replace tails[1]	[2, 3]
7	2 = len	append	[2, 3, 7]
101	3 = len	append	[2, 3, 7, 101]
18	3	replace tails[3]	[2, 3, 7, 18]

Answer 4. Two moments to read carefully:

• 9 then 2 both replaced tails[0]. Neither extended anything; each just made a length-1 run cheaper to continue. That is the algorithm’s only other move, and it is why the array never grows without a genuine improvement.
• 18 replaced 101 at the end. The length did not change, but a future value between 19 and 100 could now extend the run. The replacement is speculative and costs nothing.

Strictly increasing versus non-decreasing

One function call:

Requirement	Function	On [2, 2, 2]
strictly increasing	bisect_left	1
non-decreasing	bisect_right	3

bisect_left finds the first tail ≥ x, so an equal value replaces rather than extends — duplicates cannot both appear. bisect_right finds the first tail > x, so an equal value appends and duplicates chain.

Read the problem statement for which it wants. “Increasing” in LeetCode almost always means strictly; “non-decreasing” is stated when it is meant.

The variant map

Several problems that look nothing like LIS are LIS after a sort. The reduction is the transferable part.

Problem	Sort by	Then LIS on	The tie-break detail
354 Russian Doll Envelopes	width ascending	height	equal widths → height descending, so same-width envelopes cannot chain
646 Maximum Length of Pair Chain	first element	second	greedy by second element is also $O(n \log n)$ and simpler
452 Min Arrows to Burst Balloons	end coordinate	—	greedy: count non-overlapping groups
1671 Min Removals to Make Mountain	—	LIS from left and from right	combine at each peak
300 LIS	—	the values	the base case

LC 354 and why the descending tie-break is essential

Sort envelopes by width ascending, then find the LIS of the heights. But two envelopes of the same width can never nest, and if equal widths are sorted by height ascending, their heights form an increasing run and the LIS counts them as nestable — an over-count.

Sorting equal widths by height descending makes those heights a decreasing run, so the LIS can pick at most one of them. One comparator detail, and without it the answer is wrong on any input with repeated widths.

Complexity

Approach	Time	Space	Reconstructs the sequence?
$O(n^2)$ DP	$O(n^2)$	$O(n)$	yes, with a parent array
Patience sorting	$O(n \log n)$	$O(n)$	only with extra bookkeeping
Sort + LIS (LC 354)	$O(n \log n)$	$O(n)$	yes, with extra arrays

$O(n \log n)$ is optimal for comparison-based LIS. Explain the $O(n^2)$ version first — it is easier to state correctly and it reconstructs for free — then offer patience sorting as the improvement. Leading with the clever version and fumbling the tails semantics is a worse outcome than the straightforward one done well.

Pitfalls

• Returning dp[-1] in the $O(n^2)$ version. The answer is max(dp); the best run need not end at the last element.
• Treating tails as the answer sequence. It is not a subsequence. Only its length is meaningful.
• Using bisect_left when the problem says non-decreasing. Or bisect_right when it says strictly increasing. One call, opposite answers on duplicates.
• Forgetting the descending height tie-break in LC 354. Silently over-counts on repeated widths.
• Applying LIS to a contiguous requirement. “Longest increasing subarray” is a single $O(n)$ pass, not this.
• Claiming reconstruction is free. It needs a parent array and the index of the final append. Say so rather than implying tails suffices.

Interview follow-ups

They ask	What they’re checking	The answer
“What does tails[k] mean?”	Whether you understand the invariant	The smallest value that can end an increasing run of length k+1. That is why the array is sorted and why the binary search is valid
“Is tails the answer subsequence?”	The standard trap	No. On [1,3,5,2] it ends as [1,2,5], which is not a subsequence of the input. Only the length is correct
“Then how do you recover the sequence?”	Whether you know the cost	A parent array recording which index each element extended, plus the index of the final append; then walk backwards. $O(n)$ extra space
“Handle non-decreasing instead”	Precision	Swap bisect_left for bisect_right. Nothing else changes
“Solve Russian Doll Envelopes”	Whether you see the reduction	Sort by width ascending with equal widths by height descending, then LIS on heights. The tie-break is what stops same-width envelopes chaining
“Why is $O(n \log n)$ optimal?”	Bounds awareness	Comparison-based LIS is $\Omega(n \log n)$ by reduction from sorting. A faster algorithm would need to exploit structure in the values

Practice

4 problems

0 easy3 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○300Longest Increasing SubsequencemediumNeetCode 150Blind 75LeetCode Top Interview 150googlemicrosoftbytedanceuber
• ○452Minimum Number of Arrows to Burst BalloonsmediumLeetCode Top Interview 150
• ○646Maximum Length of Pair Chainmedium
• ○354Russian Doll Envelopeshard

Exercises

LC 300 — Longest Increasing Subsequence · Medium

pch.exerciseTag pch.exerciseTitle

LC 354 — Russian Doll Envelopes · Hard

pch.exerciseTag pch.exerciseTitle

Reconstruct the actual subsequence

pch.exerciseTag pch.exerciseTitle

Self-check

pch.quizTag LIS variants — self-check

1. What does tails[k] hold in patience sorting?

   A The k-th element of the longest increasing subsequence B The smallest value that can end an increasing run of length k+1, given what has been seen so far C The largest value seen at position k D The count of runs of length k
   pch.quizShowAnswer

   B — The smallest value that can end an increasing run of length k+1, given what has been seen so far — This is why tails is sorted — a longer run must end at a value at least as large as a shorter run's best tail — and therefore why the binary search is valid.

2. Is the final tails array a valid increasing subsequence of the input?

   A Yes, always B No — on [1,3,5,2] it ends as [1,2,5], and 2 appears after 5 in the input. Only the LENGTH is correct C Only if the input has no duplicates D Only for strictly increasing sequences
   pch.quizShowAnswer

   B — No — on [1,3,5,2] it ends as [1,2,5], and 2 appears after 5 in the input. Only the LENGTH is correct — The standard trap. tails mixes tails from different runs at different times. Recovering a real subsequence needs a parent array plus the index of the final append.

3. The problem asks for the longest NON-DECREASING subsequence. What changes?

   A Nothing B Swap bisect_left for bisect_right, so an equal value appends rather than replaces C Sort the array first D Use the O(n squared) version
   pch.quizShowAnswer

   B — Swap bisect_left for bisect_right, so an equal value appends rather than replaces — One call. On [2,2,2] bisect_left gives 1 and bisect_right gives 3 — read the statement for which is wanted.

4. In Russian Doll Envelopes, why sort equal widths by height DESCENDING?

   A For stability B Because two envelopes of the same width can never nest — descending heights form a decreasing run, so the LIS picks at most one of them C To make the binary search work D It makes no difference
   pch.quizShowAnswer

   B — Because two envelopes of the same width can never nest — descending heights form a decreasing run, so the LIS picks at most one of them — With ascending heights, same-width envelopes form an increasing run and the LIS counts them as nestable — an over-count. One comparator detail decides correctness.

5. Which version should you explain first in an interview?

   A Patience sorting, since it is optimal B The O(n squared) DP — easier to state correctly and it reconstructs for free — then offer patience sorting as the improvement C Neither; use a library function D Whichever comes to mind
   pch.quizShowAnswer

   B — The O(n squared) DP — easier to state correctly and it reconstructs for free — then offer patience sorting as the improvement — Leading with the clever version and fumbling the tails semantics is a worse outcome than the straightforward one done well. Offering the improvement afterwards shows you know both.

Recall card

• Cue — longest subsequence with an ordering condition; or minimum groups (same number, Dilworth); or longest chain of pairs.
• tails[k] — the smallest value that can end a run of length k + 1. Sorted for free, which is what licenses the binary search.
• tails is not a subsequence. Length only. Reconstruction needs parent pointers plus the last append index.
• Strict vs non-decreasing — bisect_left vs bisect_right. One call.
• The reduction — sort by one coordinate, LIS on the other. LC 354’s tie-break is equal widths by height descending.
• Complexity — $O(n \log n)$, optimal for comparison-based. Explain $O(n^2)$ first.

Recap

• Patience sorting computes the LIS length in $O(n \log n)$ by maintaining the smallest possible tail per run length.
• That array is sorted by construction, which is why binary search applies — and it is not the answer sequence, which is the error to avoid stating.
• One bisect call distinguishes strictly increasing from non-decreasing.
• Sorting by one coordinate and running LIS on the other solves the pair-chain family; the tie-break on equal first coordinates is where correctness lives.

Next: Bitmask and Tree DP — when the state is a set rather than an index.