Prerequisites
Before attempting this problem, you should be comfortable with:
- Sorting with custom comparators - Sorting by multiple criteria (width ascending, height descending for equal widths)
- Longest Increasing Subsequence (LIS) - The classic DP problem that this reduces to after sorting
- Dynamic Programming - Both top-down (memoization) and bottom-up approaches for optimization problems
- Binary Search - Used in the O(n log n) LIS solution to efficiently find insertion positions
1. Dynamic Programming (Top-Down)
Intuition
This problem is essentially finding the longest chain of envelopes where each envelope strictly contains the previous one. If we sort envelopes by width, we only need to find the longest increasing subsequence (LIS) of heights. The trick is to sort by width ascending, but when widths are equal, sort by height descending. This prevents envelopes with the same width from being part of the same chain, since we need strictly greater dimensions for both.
Algorithm
- Sort envelopes by width ascending. For equal widths, sort by height descending.
- Extract the heights into an array.
- Use memoized recursion to compute
LISon the heights:- For each index
i, recursively find the longest subsequence starting fromi. - Check all indices
j > iwhereheights[j] > heights[i], taking the maximum.
- For each index
- Return the maximum
LISvalue across all starting positions.
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
n = len(envelopes)
envelopes.sort(key=lambda x: (x[0], -x[1]))
def lis(nums):
n = len(nums)
memo = [-1] * n
def dfs(i):
if memo[i] != -1:
return memo[i]
LIS = 1
for j in range(i + 1, n):
if nums[i] < nums[j]:
LIS = max(LIS, 1 + dfs(j))
memo[i] = LIS
return LIS
return max(dfs(i) for i in range(n))
return lis([e[1] for e in envelopes])Time & Space Complexity
- Time complexity:
- Space complexity:
2. Dynamic Programming (Bottom-Up)
Intuition
Instead of using recursion, we can build the solution iteratively from right to left. For each position, we compute the length of the longest increasing subsequence starting from that position by looking at all valid successors. This bottom-up approach avoids the overhead of recursion and explicitly fills a DP table.
Algorithm
- Sort envelopes by width ascending, height descending for equal widths.
- Extract heights into an array.
- Create a
DParray whereLIS[i]represents the longest increasing subsequence starting at indexi. - Iterate from right to left:
- For each index
i, check allj > iwhereheights[j] > heights[i]. - Update
LIS[i] = max(LIS[i], 1 + LIS[j]).
- For each index
- Return the maximum value in the
LISarray.
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
n = len(envelopes)
envelopes.sort(key=lambda x: (x[0], -x[1]))
def lis(nums):
LIS = [1] * n
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
if nums[i] < nums[j]:
LIS[i] = max(LIS[i], 1 + LIS[j])
return max(LIS)
return lis([e[1] for e in envelopes])Time & Space Complexity
- Time complexity:
- Space complexity:
3. Dynamic Programming + Binary Search
Intuition
The standard LIS problem can be solved in O(n log n) using binary search. We maintain a list where each position stores the smallest ending value of all increasing subsequences of that length. For each new element, we either extend the longest subsequence or replace an existing ending value to allow for potentially longer subsequences later. Binary search finds the correct position efficiently.
Algorithm
- Sort envelopes by width ascending, height descending for equal widths.
- Extract heights into an array.
- Initialize an empty list
dpthat will store the smallest tail values for subsequences of each length. - For each height:
- If it's larger than the last element in
dp, append it (extends the longest subsequence). - Otherwise, use binary search to find the first element in
dpthat is greater than or equal to the current height, and replace it.
- If it's larger than the last element in
- The length of
dpis the answer.
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
envelopes.sort(key=lambda x: (x[0], -x[1]))
def lis(nums):
dp = []
dp.append(nums[0])
LIS = 1
for i in range(1, len(nums)):
if dp[-1] < nums[i]:
dp.append(nums[i])
LIS += 1
continue
idx = bisect_left(dp, nums[i])
dp[idx] = nums[i]
return LIS
return lis([e[1] for e in envelopes])Time & Space Complexity
- Time complexity:
- Space complexity:
4. Segment Tree
Intuition
A segment tree can efficiently answer range maximum queries, which helps compute LIS. For each height, we query the maximum LIS length among all smaller heights, add one, and update the tree with this new value. Coordinate compression reduces the height values to a manageable range. This approach achieves the same O(n log n) complexity as binary search but offers a different perspective using range queries.
Algorithm
- Sort envelopes by width ascending, height descending for equal widths.
- Extract and compress heights to consecutive integers starting from 0.
- Build a segment tree that supports range maximum queries and point updates.
- For each compressed height
h:- Query the maximum
LISvalue in the range[0, h - 1]. - The current
LISending athisquery result + 1. - Update the segment tree at position
hwith this value.
- Query the maximum
- Return the maximum
LISvalue found.
class SegmentTree:
def __init__(self, N):
self.n = N
while (self.n & (self.n - 1)) != 0:
self.n += 1
self.tree = [0] * (2 * self.n)
def update(self, i, val):
self.tree[self.n + i] = val
j = (self.n + i) >> 1
while j >= 1:
self.tree[j] = max(self.tree[j << 1], self.tree[j << 1 | 1])
j >>= 1
def query(self, l, r):
if l > r:
return 0
res = float('-inf')
l += self.n
r += self.n + 1
while l < r:
if l & 1:
res = max(res, self.tree[l])
l += 1
if r & 1:
r -= 1
res = max(res, self.tree[r])
l >>= 1
r >>= 1
return res
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
n = len(envelopes)
envelopes.sort(key=lambda x: (x[0], -x[1]))
def lis(nums):
def compress(arr):
sortedArr = sorted(set(arr))
order = []
for num in arr:
order.append(bisect_left(sortedArr, num))
return order
nums = compress(nums)
n = len(nums)
segTree = SegmentTree(n)
LIS = 0
for num in nums:
curLIS = segTree.query(0, num - 1) + 1
segTree.update(num, curLIS)
LIS = max(LIS, curLIS)
return LIS
return lis([e[1] for e in envelopes])Time & Space Complexity
- Time complexity:
- Space complexity:
Common Pitfalls
Sorting Heights in Wrong Order for Equal Widths
The most critical mistake is sorting by height ascending when widths are equal. This allows multiple envelopes with the same width to be included in the LIS, violating the strict containment requirement. When widths are equal, sort heights in descending order to ensure only one envelope per width can be selected.
Using Non-Strict Inequality for Containment
Some solutions check width1 <= width2 and height1 <= height2 instead of strict inequality. Envelopes must strictly contain each other, meaning both dimensions must be strictly greater. Using <= incorrectly allows envelopes of equal size to be nested.
Applying Standard LIS Without Dimension Reduction
Attempting to run LIS on both dimensions simultaneously leads to an incorrect or overly complex solution. The key insight is that after sorting by width, the problem reduces to finding LIS on heights alone. Failing to recognize this reduction results in unnecessary complexity or wrong answers.
Off-by-One Errors in Binary Search
When implementing the O(n log n) LIS solution, using the wrong binary search variant causes errors. You need to find the first element greater than or equal to the current height (lower bound), not strictly greater. Using upper bound or incorrect comparisons leads to wrong LIS lengths.