In this guide, you will get 354. Russian Doll Envelopes LeetCode Solution with the best time and space complexity. The solution to Russian Doll Envelopes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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]).
354. Russian Doll Envelopes LeetCode Solution in C++
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
ranges::sort(envelopes, [](const auto& a, const auto& b) {
return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
});
// Same as 300. Longest Increasing Subsequence
int ans = 0;
vector<int> dp(envelopes.size());
for (const vector<int>& e : envelopes) {
int l = 0;
int r = ans;
while (l < r) {
const int m = (l + r) / 2;
if (dp[m] >= e[1])
r = m;
else
l = m + 1;
}
dp[l] = e[1];
if (l == ans)
++ans;
}
return ans;
}
}; /* code provided by PROGIEZ */
354. Russian Doll Envelopes LeetCode Solution in Java
class Solution {
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes,
(a, b) -> a[0] == b[0] ? Integer.compare(b[1], a[1]) : Integer.compare(a[0], b[0]));
// Same as 300. Longest Increasing Subsequence
int ans = 0;
int[] dp = new int[envelopes.length];
for (int[] e : envelopes) {
int i = Arrays.binarySearch(dp, 0, ans, e[1]);
if (i < 0)
i = -(i + 1);
dp[i] = e[1];
if (i == ans)
++ans;
}
return ans;
}
} // code provided by PROGIEZ
354. Russian Doll Envelopes LeetCode Solution in Python
class Solution:
def maxEnvelopes(self, envelopes: list[list[int]]) -> int:
envelopes.sort(key=lambda x: (x[0], -x[1]))
# Same as 300. Longest Increasing Subsequence
ans = 0
dp = [0] * len(envelopes)
for _, h in envelopes:
l = 0
r = ans
while l < r:
m = (l + r) // 2
if dp[m] >= h:
r = m
else:
l = m + 1
dp[l] = h
if l == ans:
ans += 1
return ans # code by PROGIEZ
