Problem
You have envelopes with widths and heights. One envelope fits inside another if both dimensions are strictly larger. Find the max number of envelopes you can nest.
Example
Input: [[5,4],[6,4],[6,7],[2,3]]
Output: 3Solution
Sort by width ascending, height descending (so we don’t pick two with same width). Then find longest increasing subsequence in heights.
from bisect import bisect_left
def max_envelopes(envelopes):
envelopes.sort(key=lambda x: (x[0], -x[1]))
tails = []
for _, h in envelopes:
i = bisect_left(tails, h)
if i == len(tails): tails.append(h)
else: tails[i] = h
return len(tails)function maxEnvelopes(envelopes) {
envelopes.sort((a, b) => a[0] - b[0] || b[1] - a[1]);
const tails = [];
for (const [, h] of envelopes) {
let l = 0, r = tails.length;
while (l < r) {
const mid = (l + r) >> 1;
if (tails[mid] < h) l = mid + 1;
else r = mid;
}
tails[l] = h;
}
return tails.length;
}int maxEnvelopes(vector<vector<int>>& envelopes) {
sort(envelopes.begin(), envelopes.end(), [](auto& a, auto& b) {
return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1];
});
vector<int> tails;
for (auto& e : envelopes) {
auto it = lower_bound(tails.begin(), tails.end(), e[1]);
if (it == tails.end()) tails.push_back(e[1]);
else *it = e[1];
}
return tails.size();
}public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
int[] tails = new int[envelopes.length];
int size = 0;
for (int[] e : envelopes) {
int l = 0, r = size;
while (l < r) {
int mid = (l + r) >> 1;
if (tails[mid] < e[1]) l = mid + 1;
else r = mid;
}
tails[l] = e[1];
if (l == size) size++;
}
return size;
}Complexity
- Time: O(n log n)
- Space: O(n)
Explanation
Sorting heights descending within same width prevents picking both. Then we just need LIS of heights, which is O(n log n) with binary search.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?