Skip to content

354. Russian Doll Envelopes

On LeetCode ->

Problem

Given envelopes as [width, height], return the longest nesting chain where both dimensions strictly increase; envelopes cannot be rotated.

Input:  [[5,4], [6,4], [6,7], [2,3]]
Chain:  [2,3] -> [5,4] -> [6,7]
Output: 3

Key trick

Sort by width ascending but height descending for equal widths, then find the strictly increasing longest subsequence of heights using binary search.

Descending heights prevent equal-width envelopes from appearing in the same subsequence.

Trap

  • Sorting both dimensions ascending incorrectly allows equal-width envelopes to contribute to the height subsequence.
  • Using bisect_right allows equal heights, but nesting requires strict growth.
  • The straightforward dynamic programming solution takes \(O(n^2)\) and times out for \(10^5\) envelopes.

Why is it interesting?

A two-dimensional ordering problem becomes a one-dimensional longest increasing subsequence problem through a careful tie-breaking sort.

Python solution

import bisect


class Solution:
    def maxEnvelopes(self, envelopes: list[list[int]]) -> int:
        # Equal widths use descending heights so they cannot both enter the LIS.
        envelopes.sort(key=lambda envelope: (envelope[0], -envelope[1]))

        # tails[i] is the smallest possible ending height for a chain
        # containing i + 1 envelopes.
        tails = []

        for _, height in envelopes:
            i = bisect.bisect_left(tails, height)

            if i == len(tails):
                tails.append(height)
            else:
                tails[i] = height

        return len(tails)

Time complexity: \(O(n \log n)\).

Space complexity: \(O(n)\).

Comment on my solution

Your dynamic programming recurrence is correct, and lexicographic sorting is safe because you explicitly require both dimensions to increase.

The issue is the nested loop, which makes the solution \(O(n^2)\) and too slow for \(n = 10^5\). Replacing the recurrence with the binary-search LIS technique reduces it to \(O(n \log n)\).

# Ideas:
# - it seems to be classic LIS where order relation is determine by both endpoint
#   - [w1, h1] < [w2, h2] iff w1 < w2 and h1 < h2
# - What to do when (pair not comparable)
#   - w1 < w2 but h1 >= h2
#   - h1 < h2 but w1 >= w2
# - In O(n^2) we can do dp[i] max length of russian doll ending at envelopes[i]
# - As I hit Time Limit Exceeded error, there's should be an
#   algo with better time complexity


# WRONG
# Time Limit Exceeded: 85/87 testcases passed
class Solution:
    def maxEnvelopes(self, envelopes: list[list[int]]) -> int:
        n = len(envelopes)
        envelopes.sort()
        dp = [1] * n
        best = 1
        for i in range(1,n):
            wi, hi = envelopes[i][0], envelopes[i][1]
            for j in range(i):
                wj, hj = envelopes[j][0], envelopes[j][1]
                if wj < wi and hj < hi:
                    dp[i] = max(dp[i], dp[j] + 1)
            best = max(best, dp[i])
        return best