You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.
One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.
Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).
Note: You cannot rotate an envelope.
Example 1:
Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
Example 2:
Input: envelopes = [[1,1],[1,1],[1,1]] Output: 1
Constraints:
1 <= envelopes.length <= 5000envelopes[i].length == 21 <= wi, hi <= 104
Companies:
Google, ByteDance, Uber, Amazon, Microsoft, Apple
Related Topics:
Array, Binary Search, Dynamic Programming, Sorting
Similar Questions:
Since there are two dimensions, we can sort one of the dimensions, say width w, to simplify the problem. When we scan from left to right, the width dimension is already sorted so we can ignore this dimension.
[[5,4],[6,4],[6,7],[2,3]]
// after sorting by `w`
[[2,3],[5,4],[6,4],[6,7]]
// Ignoring the `w` dimension
[3,4,4,7]
This problem becomes finding the longest increasing subsequence (LIS). But one caveat is that [3,4,7] might implies [[2,3],[6,4],[6,7]] which is invalid. To avoid this issue, we can sort by height after sorting by width first.
[[5,4],[6,4],[6,7],[2,3]]
// after sorting by `w`, then by `h`
[[2,3],[5,4],[6,7],[6,4]]
// Ignoring the `w` dimension
[3,4,7,4] // Now we can't use [6,4] with [6,7]
// OJ: https://leetcode.com/problems/russian-doll-envelopes/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
// Ref: https://leetcode.com/problems/russian-doll-envelopes/discuss/82763/Java-NLogN-Solution-with-Explanation
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& A) {
sort(begin(A), end(A), [](auto &a, auto &b) { return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1]; });
vector<int> dp;
for (auto &v : A) {
auto it = lower_bound(begin(dp), end(dp), v[1]);
if (it == end(dp)) dp.push_back(v[1]);
else *it = v[1];
}
return dp.size();
}
};