We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Russian Doll Envelopes

Number: 354

Difficulty: Hard

Paid? No

Companies: Google, Amazon, Atlassian, Microsoft, Intuit, Sprinklr

Problem Description

Given a list of envelopes where each envelope is represented as [width, height], determine the maximum number of envelopes you can nest (Russian doll) such that for envelope A to fit into envelope B, both A's width and height are strictly less than B's. Note that rotating envelopes is not allowed.

Key Insights

  • Sort envelopes by width in ascending order and, if the widths are equal, by height in descending order.
  • Sorting in this manner allows us to avoid conflicts when envelopes share the same width.
  • After sorting, the problem reduces to finding the Longest Increasing Subsequence (LIS) based solely on heights.
  • Utilize binary search within the LIS algorithm to achieve an efficient O(n log n) solution.

Space and Time Complexity

Time Complexity: O(n log n), where n is the number of envelopes.
Space Complexity: O(n), required for the dynamic list used in the LIS solution.

Solution

The algorithm first sorts the envelopes by their width in increasing order. For envelopes with the same width, sorting by height in descending order ensures that only one envelope of the same width can be considered in the nesting sequence. Then, we extract the heights and use a binary search-based approach to compute the longest increasing subsequence (LIS) of heights, which represents the maximum number of envelopes we can nest. The list maintained during the LIS calculation stores the smallest possible tail for increasing subsequences of different lengths, allowing efficient updating and extension of potential sequences.

Code Solutions

# Python solution with detailed comments
def maxEnvelopes(envelopes):
    # Sort envelopes primarily by width in ascending order and
    # by height in descending order if widths are equal.
    envelopes.sort(key=lambda x: (x[0], -x[1]))
    
    lis = []  # List to track the Longest Increasing Subsequence (LIS) of heights
    import bisect
    for _, height in envelopes:
        # Find the position where 'height' can be inserted to maintain lis in sorted order.
        pos = bisect.bisect_left(lis, height)
        if pos == len(lis):
            # 'height' is greater than all elements in lis; extend lis.
            lis.append(height)
        else:
            # Replace element to keep the potential of a longer increasing sequence.
            lis[pos] = height
    return len(lis)

# Example usage
print(maxEnvelopes([[5,4],[6,4],[6,7],[2,3]]))
← Back to All Questions