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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Russian Doll Envelopes

Difficulty: Hard

Problem Description

You are given a 2D array of integers envelopes where envelopes[i] = [w_i, h_i] 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). You cannot rotate an envelope.

Key Insights

  • The problem is essentially about finding the longest increasing subsequence (LIS) based on two dimensions (width and height).
  • Sorting the envelopes first by width (in ascending order) and then by height (in descending order) helps in simplifying the problem to finding the LIS on heights.
  • By sorting in this way, we ensure that envelopes of the same width cannot be nested, as their heights will be in descending order.

Space and Time Complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

Solution

To solve the problem, we can follow these steps:

  1. Sort the envelopes array first by width in ascending order and then by height in descending order.
  2. Extract the heights from the sorted envelopes and find the longest increasing subsequence (LIS) on these heights using binary search.
  3. The length of the LIS will give us the maximum number of envelopes that can be nested.

Data Structures and Algorithms

  • We use a list to store heights and a binary search algorithm to efficiently find the position to replace elements while calculating the LIS.

Code Solutions

def maxEnvelopes(envelopes):
    # Step 1: Sort the envelopes
    envelopes.sort(key=lambda x: (x[0], -x[1]))
    
    # Step 2: Extract heights and find LIS
    heights = [h for _, h in envelopes]
    lis = []
    
    for h in heights:
        # Binary search for the current height
        left, right = 0, len(lis)
        while left < right:
            mid = (left + right) // 2
            if lis[mid] < h:
                left = mid + 1
            else:
                right = mid
        # If left is equal to the length of lis, we append the height
        if left == len(lis):
            lis.append(h)
        else:
            lis[left] = h
            
    return len(lis)
← Back to All Questions