Leetcode Problem 354. Russian Doll Envelopes

354. Russian Doll Envelopes

Leetcode Solutions

Sort + Longest Increasing Subsequence (LIS)

  1. Sort the envelopes array. First by width in ascending order, and then by height in descending order for envelopes with the same width.
  2. Initialize an empty list dp to store the ends of the increasing subsequences.
  3. Iterate over the sorted envelopes, and for each envelope: a. Use binary search to find the index i in dp where the current envelope's height can be placed (or replace an existing one). b. If i is equal to the length of dp, append the height to dp. c. Otherwise, replace dp[i] with the current envelope's height.
  4. The length of dp is the maximum number of envelopes that can be Russian dolled.
UML Thumbnail

Dynamic Programming Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...