Russian Doll Envelopes
Hard · Binary Search · Explanation and code example
Segment Tree
How it works
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.
Steps
- 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.
Complexity
- Time complexity:
O(n log n) - Space complexity:
O(n)
Things to watch for
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.
Python code example
from typing import List
from bisect import bisect_left
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])
C++ code example
class SegmentTree {
public:
int n;
vector<int> tree;
SegmentTree(int N) {
n = N;
while (n & (n - 1)) {
n++;
}
tree.resize(2 * n);
}
void update(int i, int val) {
tree[n + i] = val;
int j = (n + i) >> 1;
while (j >= 1) {
tree[j] = max(tree[j << 1], tree[j << 1 | 1]);
j >>= 1;
}
}
int query(int l, int r) {
if (l > r) {
return 0;
}
int res = INT_MIN;
l += n;
r += n + 1;
while (l < r) {
if (l & 1) {
res = max(res, tree[l]);
l++;
}
if (r & 1) {
r--;
res = max(res, tree[r]);
}
l >>= 1;
r >>= 1;
}
return res;
}
};
class Solution {
int lis(vector<int>& nums) {
vector<int> sortedArr = nums;
sort(sortedArr.begin(), sortedArr.end());
sortedArr.erase(unique(sortedArr.begin(),
sortedArr.end()), sortedArr.end());
vector<int> order(nums.size());
for (int i = 0; i < nums.size(); i++) {
order[i] = lower_bound(sortedArr.begin(), sortedArr.end(),
nums[i]) - sortedArr.begin();
}
int n = sortedArr.size();
SegmentTree segTree(n);
int LIS = 0;
for (int num : order) {
int curLIS = segTree.query(0, num - 1) + 1;
segTree.update(num, curLIS);
LIS = max(LIS, curLIS);
}
return LIS;
}
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
int n = envelopes.size();
sort(envelopes.begin(), envelopes.end(),
[](const vector<int>& a, const vector<int>& b) {
if (a[0] != b[0]) return a[0] < b[0];
return a[1] > b[1];
});
vector<int> heights(n);
for (int i = 0; i < n; ++i) heights[i] = envelopes[i][1];
return lis(heights);
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.