Jobs

Interviews

Discussions

Russian Doll Envelopes

Hard

Asked by:

More companies

281 views

Topics:

ArraysBinary SearchDynamic Programming

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).

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]).

Example 2:

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1

Constraints:

1 <= envelopes.length <= 10⁵
envelopes[i].length == 2
1 <= w_i, h_i <= 10⁵

Try coding it in LeetCode

Russian Doll Envelopes

Hard

Asked by:

More companies

281 views

Topics:

ArraysBinary SearchDynamic Programming

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).

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]).

Example 2:

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1

Constraints:

1 <= envelopes.length <= 10⁵
envelopes[i].length == 2
1 <= w_i, h_i <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the width and height of the envelopes? Can they be zero or negative?
If no envelopes can be nested, what should the function return?
If there are duplicate envelopes (same width and height), how should they be handled? Can they be considered nested within each other?
Is the input list guaranteed to be non-null? What should be the return if the input is null or empty?
Can I assume the list contains only valid envelope representations (pairs of integers)? Or should I validate the input?

Brute Force Solution

Approach

The brute force approach to fitting Russian doll envelopes is like trying every single possible arrangement to see which one allows you to fit the most envelopes inside each other. We check every possible nesting order, making sure each envelope can actually fit inside the next.

Here's how the algorithm would work step-by-step:

Consider each envelope as a potential starting envelope.
For each starting envelope, try every other envelope to see if it can fit inside.
If an envelope fits, consider it as the next envelope in the chain.
Continue trying to add envelopes to the chain, one by one, making sure each new envelope fits inside the previous one.
Keep track of the longest chain of nested envelopes that you find.
Repeat this process, starting with each envelope as a possible starting point.
Once you have tried every possible arrangement, the longest chain you found is your answer.

Code Implementation

def max_envelopes_brute_force(envelopes):
    number_of_envelopes = len(envelopes)
    max_nested_envelopes = 0

    for starting_envelope_index in range(number_of_envelopes):
        # Consider each envelope as a starting point.
        current_max_nested = 1
        
        def can_fit(inner_envelope, outer_envelope):
            return inner_envelope[0] < outer_envelope[0] and inner_envelope[1] < outer_envelope[1]
        
        def find_max_nested(current_envelope_index, current_chain_length):
            nonlocal current_max_nested
            current_max_nested = max(current_max_nested, current_chain_length)

            # Explore other envelopes to potentially add to the chain.
            for next_envelope_index in range(number_of_envelopes):
                if next_envelope_index != current_envelope_index:
                    if can_fit(envelopes[current_envelope_index], envelopes[next_envelope_index]):
                        find_max_nested(next_envelope_index, current_chain_length + 1)

        find_max_nested(starting_envelope_index, 1)
        max_nested_envelopes = max(max_nested_envelopes, current_max_nested)

    return max_nested_envelopes

Big(O) Analysis

Time Complexity

O(n!) – The algorithm considers each envelope as a potential starting point, leading to n possibilities. For each starting envelope, it explores all possible orderings of the remaining envelopes to find the longest nested chain. Generating all permutations of n envelopes requires examining n! (n factorial) possible arrangements in the worst case. Checking the nesting order within each permutation takes O(n) time. Therefore, the overall time complexity is O(n * n!), which simplifies to O(n!).

Space Complexity

O(1) – The described brute force approach primarily uses a few variables to track the current starting envelope, the potential next envelope in the chain, and the length of the longest chain found so far. These variables consume a constant amount of space, irrespective of the number of envelopes, N. No auxiliary data structures like lists or maps that scale with the input size are created. Therefore, the space complexity remains constant, O(1).

Optimal Solution

Approach

The key idea is to sort the envelopes in a clever way, and then find the longest increasing sequence. This avoids checking every possible combination by focusing on building a valid sequence step-by-step.

Here's how the algorithm would work step-by-step:

First, organize the envelopes. Sort them by their width from smallest to largest. If two envelopes have the same width, sort them by their height from largest to smallest. This is a crucial step to make the next part work.
Now, consider only the heights of the envelopes in the sorted order. Find the longest sequence of heights where each height is strictly bigger than the previous one in the sequence.
The length of this longest increasing sequence represents the maximum number of envelopes you can nest inside each other.

Code Implementation

def russian_doll_envelopes(envelopes):    if not envelopes:        return 0    # Sort by width (asc) and height (desc)    envelopes.sort(key=lambda x: (x[0], -x[1]))    envelope_heights = [envelope[1] for envelope in envelopes]    def longest_increasing_subsequence(nums):        tails = []        # Iterate through the heights        for height in nums:            if not tails or height > tails[-1]:                tails.append(height)            else:                # Binary search to find the smallest tail >= height                left, right = 0, len(tails) - 1                while left <= right:                    mid = (left + right) // 2                    if tails[mid] < height:                        left = mid + 1                    else:                        right = mid - 1                tails[left] = height        # The length of tails is the LIS length        return len(tails)
    #Compute the LIS based on heights after sorting
    max_envelopes = longest_increasing_subsequence(envelope_heights)
    return max_envelopes

Big(O) Analysis

Time Complexity

O(n log n) – Sorting the envelopes initially takes O(n log n) time, where n is the number of envelopes. The longest increasing subsequence (LIS) is found on the heights, after the sort. Using an efficient algorithm like binary search to find the position for insertion in the LIS takes O(log n) time for each height. Since we iterate through all n heights, finding the LIS takes O(n log n) time. Therefore, the dominant operation is the sorting and LIS each taking O(n log n), and the entire algorithm is bounded by O(n log n).

Space Complexity

O(N) – The algorithm sorts the envelopes, which can be done in-place with algorithms like heapsort or quicksort with O(1) auxiliary space in some implementations, however, many standard library sort functions use O(N) space (e.g., merge sort). Subsequently, it extracts the heights of the envelopes into a new array of size N, where N is the number of envelopes. The longest increasing subsequence calculation, if done using dynamic programming, may require an array of size N to store the tails of the increasing subsequences. Therefore, the overall auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Input envelopes array is null or empty.	Return 0 if the input array is null or has a length of 0, as no envelopes can be nested.
Input envelopes array contains envelopes with zero width or height.	Filter out envelopes with zero width or height as they cannot contain any other envelope.
Input envelopes array contains envelopes with negative width or height.	Handle invalid input by throwing an exception or filtering them out since envelope dimensions cannot be negative.
All envelopes have the same width.	Sorting by width first breaks the ties with height in descending order ensuring only increasing height is considered for nesting when widths are equal.
Envelopes can be nested in multiple valid ways with the same maximum number of nested envelopes.	The longest increasing subsequence algorithm will find one of the valid solutions, which is acceptable.
Integer overflow potential during height comparisons if height values are very large.	Use appropriate data types (e.g., long) to avoid potential integer overflow during height comparison.
Input array is extremely large.	Ensure the algorithm using binary search for LIS scales efficiently to handle large input sizes.
All envelopes have the same width and height	After sorting the envelopes will be in the same order, resulting in a longest increasing subsequence of length 1.

Input envelopes array is null or empty.

How to Handle:

Return 0 if the input array is null or has a length of 0, as no envelopes can be nested.

Input envelopes array contains envelopes with zero width or height.

How to Handle:

Filter out envelopes with zero width or height as they cannot contain any other envelope.

Input envelopes array contains envelopes with negative width or height.

How to Handle:

Handle invalid input by throwing an exception or filtering them out since envelope dimensions cannot be negative.

All envelopes have the same width.

How to Handle:

Sorting by width first breaks the ties with height in descending order ensuring only increasing height is considered for nesting when widths are equal.

Envelopes can be nested in multiple valid ways with the same maximum number of nested envelopes.

How to Handle:

The longest increasing subsequence algorithm will find one of the valid solutions, which is acceptable.

Integer overflow potential during height comparisons if height values are very large.

How to Handle:

Use appropriate data types (e.g., long) to avoid potential integer overflow during height comparison.

Input array is extremely large.

How to Handle:

Ensure the algorithm using binary search for LIS scales efficiently to handle large input sizes.

All envelopes have the same width and height

How to Handle:

After sorting the envelopes will be in the same order, resulting in a longest increasing subsequence of length 1.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the width and height of the envelopes? Can they be zero or negative?
If no envelopes can be nested, what should the function return?
If there are duplicate envelopes (same width and height), how should they be handled? Can they be considered nested within each other?
Is the input list guaranteed to be non-null? What should be the return if the input is null or empty?
Can I assume the list contains only valid envelope representations (pairs of integers)? Or should I validate the input?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider each envelope as a potential starting envelope.
For each starting envelope, try every other envelope to see if it can fit inside.
If an envelope fits, consider it as the next envelope in the chain.
Continue trying to add envelopes to the chain, one by one, making sure each new envelope fits inside the previous one.
Keep track of the longest chain of nested envelopes that you find.
Repeat this process, starting with each envelope as a possible starting point.
Once you have tried every possible arrangement, the longest chain you found is your answer.

Code Implementation

def max_envelopes_brute_force(envelopes):
    number_of_envelopes = len(envelopes)
    max_nested_envelopes = 0

    for starting_envelope_index in range(number_of_envelopes):
        # Consider each envelope as a starting point.
        current_max_nested = 1
        
        def can_fit(inner_envelope, outer_envelope):
            return inner_envelope[0] < outer_envelope[0] and inner_envelope[1] < outer_envelope[1]
        
        def find_max_nested(current_envelope_index, current_chain_length):
            nonlocal current_max_nested
            current_max_nested = max(current_max_nested, current_chain_length)

            # Explore other envelopes to potentially add to the chain.
            for next_envelope_index in range(number_of_envelopes):
                if next_envelope_index != current_envelope_index:
                    if can_fit(envelopes[current_envelope_index], envelopes[next_envelope_index]):
                        find_max_nested(next_envelope_index, current_chain_length + 1)

        find_max_nested(starting_envelope_index, 1)
        max_nested_envelopes = max(max_nested_envelopes, current_max_nested)

    return max_nested_envelopes

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, organize the envelopes. Sort them by their width from smallest to largest. If two envelopes have the same width, sort them by their height from largest to smallest. This is a crucial step to make the next part work.
Now, consider only the heights of the envelopes in the sorted order. Find the longest sequence of heights where each height is strictly bigger than the previous one in the sequence.
The length of this longest increasing sequence represents the maximum number of envelopes you can nest inside each other.

Code Implementation

def russian_doll_envelopes(envelopes):    if not envelopes:        return 0    # Sort by width (asc) and height (desc)    envelopes.sort(key=lambda x: (x[0], -x[1]))    envelope_heights = [envelope[1] for envelope in envelopes]    def longest_increasing_subsequence(nums):        tails = []        # Iterate through the heights        for height in nums:            if not tails or height > tails[-1]:                tails.append(height)            else:                # Binary search to find the smallest tail >= height                left, right = 0, len(tails) - 1                while left <= right:                    mid = (left + right) // 2                    if tails[mid] < height:                        left = mid + 1                    else:                        right = mid - 1                tails[left] = height        # The length of tails is the LIS length        return len(tails)
    #Compute the LIS based on heights after sorting
    max_envelopes = longest_increasing_subsequence(envelope_heights)
    return max_envelopes

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input envelopes array is null or empty.	Return 0 if the input array is null or has a length of 0, as no envelopes can be nested.
Input envelopes array contains envelopes with zero width or height.	Filter out envelopes with zero width or height as they cannot contain any other envelope.
Input envelopes array contains envelopes with negative width or height.	Handle invalid input by throwing an exception or filtering them out since envelope dimensions cannot be negative.
All envelopes have the same width.	Sorting by width first breaks the ties with height in descending order ensuring only increasing height is considered for nesting when widths are equal.
Envelopes can be nested in multiple valid ways with the same maximum number of nested envelopes.	The longest increasing subsequence algorithm will find one of the valid solutions, which is acceptable.
Integer overflow potential during height comparisons if height values are very large.	Use appropriate data types (e.g., long) to avoid potential integer overflow during height comparison.
Input array is extremely large.	Ensure the algorithm using binary search for LIS scales efficiently to handle large input sizes.
All envelopes have the same width and height	After sorting the envelopes will be in the same order, resulting in a longest increasing subsequence of length 1.

Input envelopes array is null or empty.

How to Handle:

Return 0 if the input array is null or has a length of 0, as no envelopes can be nested.

Input envelopes array contains envelopes with zero width or height.

How to Handle:

Filter out envelopes with zero width or height as they cannot contain any other envelope.

Input envelopes array contains envelopes with negative width or height.

How to Handle:

Handle invalid input by throwing an exception or filtering them out since envelope dimensions cannot be negative.

All envelopes have the same width.

How to Handle:

Sorting by width first breaks the ties with height in descending order ensuring only increasing height is considered for nesting when widths are equal.

Envelopes can be nested in multiple valid ways with the same maximum number of nested envelopes.

How to Handle:

The longest increasing subsequence algorithm will find one of the valid solutions, which is acceptable.

Integer overflow potential during height comparisons if height values are very large.

How to Handle:

Use appropriate data types (e.g., long) to avoid potential integer overflow during height comparison.

Input array is extremely large.

How to Handle:

Ensure the algorithm using binary search for LIS scales efficiently to handle large input sizes.

All envelopes have the same width and height

How to Handle:

After sorting the envelopes will be in the same order, resulting in a longest increasing subsequence of length 1.