Russian Doll Envelopes - Leetcode Solution

The Russian Doll Envelopes problem on Leetcode is a problem that requires you to find the maximum number of envelopes that can be nested inside each other. An envelope is a pair of integers (w, h) representing the width and the height of an envelope. You can only nest an envelope inside another if both the width and the height of the inner envelope are strictly smaller than those of the outer envelope.

Here is a detailed solution to the Russian Doll Envelopes problem:

1. Sort the envelopes array in ascending order of the width. If two envelopes have the same width, sort them in descending order of their heights. This is because if two envelopes have the same width, we cannot nest one inside the other, so we need to keep the one with the larger height outside.

2. Create an array called dp of size equal to the length of the envelopes array. Set all the values of dp to 1 initially. This array will store the maximum number of nested envelopes we can have with the ith envelope as the outermost envelope.

3. Traverse the envelopes array from left to right. For each envelope, traverse all the envelopes that come before it and check if the current envelope can be nested inside any of them. If it can, update the value of dp for the current envelope as dp[j] + 1, where j is the index of the envelope that the current envelope can be nested inside and dp[j] + 1 represents the maximum number of nested envelopes we can have with the jth envelope as the outermost envelope.

4. After we have traversed all the envelopes, the maximum number of nested envelopes we can have is the maximum value in the dp array.

Here is the Python code for this solution:

def maxEnvelopes(envelopes: List[List[int]]) -> int:
    n = len(envelopes)
    # sort envelopes in ascending order of width
    # if two envelopes have the same width, sort them in descending order of their height
    envelopes.sort(key=lambda x: (x[0], -x[1]))
    # initialize dp array to 1
    dp = [1] * n
    # traverse envelopes array and update dp array
    for i in range(n):
        for j in range(i):
            if envelopes[i][0] > envelopes[j][0] and envelopes[i][1] > envelopes[j][1]:
                dp[i] = max(dp[i], dp[j] + 1)
    # return maximum value in dp array
    return max(dp)

The time complexity of this solution is O(n^2), where n is the length of the envelopes array. However, we can optimize this solution to have a time complexity of O(n*logn) by using binary search instead of the inner loop.

1