• 1 ≤ envelopes.length ≤ 10⁵
• 1 ≤ width, height ≤ 10⁵
• Both dimensions must be strictly smaller for one envelope to fit inside another
• Envelopes may not be rotated

Strip away the packaging and this is the longest-chain problem again: pick as many envelopes as possible, arranged so that each fits inside the next. What makes it harder than a plain increasing subsequence is that "fits inside" is a condition on two numbers at once — both width and height must be strictly smaller.

With a single dimension, the input's order would matter and we would be looking for an increasing subsequence. Here the envelopes come in no particular order and we may nest them in any order we like, so we are free to sort them first — a freedom that turns out to be the whole solution.

Note the strictness: [3, 4] does not fit inside [3, 5], because their widths tie. Equal in either dimension means no nesting.

Sort by width. Now any envelope that could contain envelope i must appear later in the sorted order, so we can run exactly the longest-increasing-subsequence recurrence over heights, with an extra check on width:

def max_envelopes(envelopes):
    envelopes.sort()
    n = len(envelopes)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if envelopes[j][0] < envelopes[i][0] and envelopes[j][1] < envelopes[i][1]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

This is correct, and it is what you should write first if you are unsure. But it costs about N²/2 comparisons, and with 100000 envelopes that is five billion — far beyond what will run in time. The stated bound is telling us an O(N log N) method is expected.

Here is the idea that solves it. After sorting by width, if we could guarantee that every candidate predecessor has a strictly smaller width, the width check would become unnecessary — and the problem would collapse to a plain longest increasing subsequence over heights, which we already know how to do in O(N log N).

Sorting by width ascending gets us most of the way, but not all: envelopes with the same width are still adjacent, and those must never be nested together no matter what their heights are. If we sort ties by height ascending, disaster follows. Take [3, 4] and [3, 6]. Sorted that way, the heights read 4 then 6, which looks like a valid increasing pair, and the algorithm would happily nest two envelopes of identical width.

The fix is elegant: for equal widths, sort by height descending. Now [3, 6] comes before [3, 4], and the heights read 6 then 4 — a decrease, which no increasing subsequence can use. Two envelopes of the same width can never both be chosen, because their heights are guaranteed to appear in decreasing order. The constraint we needed has been baked into the ordering.

So the algorithm is:

from bisect import bisect_left

def max_envelopes(envelopes):
    # width ascending; on ties, height DESCENDING
    envelopes.sort(key=lambda e: (e[0], -e[1]))

    tails = []                      # tails[k] = smallest height ending a chain of length k+1
    for _, h in envelopes:
        pos = bisect_left(tails, h)
        if pos == len(tails):
            tails.append(h)
        else:
            tails[pos] = h
    return len(tails)

The second half is the patience-tails method for a longest increasing subsequence, run on the heights: tails[k] is the smallest height that any chain of length k+1 could end with. The array stays sorted, because a longer chain must end higher than the best shorter one. Overwriting an entry only ever makes a chain's ending smaller, which is strictly better for the future.

Sorting costs O(N log N) and each of the N binary searches costs O(log N), so the whole thing is O(N log N) with O(N) space. As with any patience-tails run, len(tails) is the correct length, but the contents of tails are not necessarily an actual chain.

Notice the two width-6 envelopes: [6,7] comes first because 7 is bigger. The heights are now 3, 4, 7, 4.

Run the increasing-subsequence machinery on those heights:
- 3: tails is empty, so append. tails = [3]
- 4: larger than everything, append. tails = [3, 4]
- 7: larger than everything, append. tails = [3, 4, 7]
- 4: not larger than everything. The leftmost tail ≥ 4 is at index 1, so overwrite it. tails = [3, 4, 7] — unchanged in value here, but in general this is where an improvement gets recorded.

Answer len(tails) = 3, the nesting [2,3] → [5,4] → [6,7].

Now watch the tie-break earn its keep. Had we sorted ties by height ascending, the order would have been [2,3], [5,4], [6,4], [6,7] with heights 3, 4, 4, 7. Under strict increase, 4 after 4 is still rejected by bisect_left, so this particular input survives — but change it to [[6,4],[6,5],[6,6]] and ascending ties give heights 4, 5, 6, an answer of 3, when the true answer is 1 because all three envelopes have the same width. Descending ties give 6, 5, 4 and correctly return 1.

Two ideas from this page are worth more than the problem itself.

Sort to remove a dimension. When a problem imposes conditions on several coordinates at once, sorting on one of them often makes that condition automatic, leaving a simpler one-dimensional problem behind. Ask yourself after sorting: which checks are now guaranteed by the order, and can be deleted from the loop?

Use the tie-break to encode a constraint. Ties are where sorting is under-specified, and that freedom can be spent. Here, descending heights within a width made "same width cannot nest" impossible to violate. The same manoeuvre appears in interval scheduling, in meeting-room problems, and in several sweep-line algorithms — whenever equal keys need different treatment from unequal ones.

And the general warning that comes with both: an algorithm that leans on a sort order is only as correct as that order. When you use this technique, write down in one sentence what property the sort guarantees, and check that your comparator actually delivers it.