Sorting · binary search · longest increasing subsequence
How many envelopes can fit inside one another?
Input: a list of envelopes, each with a positive width and height. An envelope fits inside another only when both dimensions are strictly smaller; rotation is not allowed. Output the maximum number that can be nested.
Sort the dimensions
Put widths in ascending order. For equal widths, put heights in descending order.
key = (width, -height)Search the heights
Widths are now ordered. Find a strictly increasing subsequence of heights with tails and lower bound: the first tail ≥ the current height.
Read the answer
Each tails slot represents an achievable nesting length. Append to grow it; replace an ending to leave more room for later envelopes. Return len(tails).
Interactive walkthrough
Watch the sort turn two dimensions into one.
Step through the ordering, each lower-bound comparison, and each change to tails.
Input · original order
↓ sort by width ↑, then height ↓ for equal widths
Sorted envelopes · width × height
Start with the envelopes
Press Next or Play to sort them, then process heights in order.
Tails · smallest ending height by length
No binary search yet.
No heights processed yet.
The subtle sorting rule
Equal widths can never nest.
Consider (2,3) and (2,4). If they appeared in ascending height order, heights 3 → 4 would look like a valid LIS even though the widths are equal. Descending height order makes them (2,4), (2,3), so a strictly increasing height subsequence can take at most one.
Strictness matters twice: equal widths are handled by the tie-break, and equal heights are handled by lower bound (≥ replaces instead of appends).
Why tails works
tails[i] is the smallest ending height found for a valid sequence of length i + 1. Replacing a larger ending preserves that length and improves the chance of extending it later. tails may mix endings from different sequences, so it is not necessarily one actual nesting chain; its length is the answer.
Sorting costs O(n log n). Each of n heights takes O(log n) search time, with O(n) extra space.
Python · sort + lower-bound LIS
The complete solution
from typing import List
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
# Equal widths need descending heights.
envelopes.sort(key=lambda pair: (pair[0], -pair[1]))
def lower_bound(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] >= target:
right = mid - 1
else:
left = mid + 1
return left
tails = []
for width, height in envelopes:
pos = lower_bound(tails, height)
if pos == len(tails):
tails.append(height)
else:
tails[pos] = height
return len(tails)