Solution: Russian Doll Envelopes

Statement

You are given a 2D array of integers, envelopes, where each element envelopes[i] = [wi, hi] represents the width and height of an envelope. An envelope can fit inside another if and only if its width and height are strictly smaller than the width and height of the other envelope. The task is to determine the maximum number of envelopes that can be nested inside each other, similar to Russian dollsRussian dolls, also known as stacking dolls or nesting dolls, are a set of wooden dolls of decreasing size placed one inside another. .

Constraints:

• $1\leq$ envelopes.length $\leq 10^3$

• envelopes[i].length $== 2$

• $1\leq$ wi, hi $\leq 10^4$

Solution

This solution uses a combination of sorting and searching techniques to determine the maximum number of envelopes that can be nested within each other, keeping in light that both the width and height of the envelope to fit must be smaller than the other envelope. The challenge in this problem is to simultaneously compare dimensions, width, and height while keeping the solution right. This is handled by sorting the envelopes by width in ascending order and, in the case of ties, sorting by height in descending order. This descending height is important because it prevents misunderstanding of envelopes with the same width. Smaller envelopes could incorrectly nest within larger ones if heights are sorted in ascending order.

Once the envelopes are sorted, the solution finds the longest increasing subsequence (LIS)The Longest Increasing Subsequence (LIS) is the longest subsequence of a given sequence in which the elements are strictly increasing. based on the height of the envelopes, treating the heights of sorted envelopes as a one-dimensional sequence. The solution uses binary search to manage the LIS, tracking the smallest possible ending heights of increasing subsequences of various lengths. For each height:

• Binary search determines the position in LIS where the current height can fit. The idea is to find the first height in LIS greater than or equal to the current height. This ensures the sequence remains sorted and allows the replacement of larger values, maintaining the smallest possible subsequences for future comparisons.

• If no such position exists (i.e., the height is greater than all values in LIS), the height is appended to LIS, meaning an extension of the LIS.

• If a valid position exists, the height replaces the value at that position in LIS, ensuring that subsequences of that length have the smallest possible ending height.

Here’s the step-by-step implementation of the solution:

1. Sort the envelopes by width in ascending order, and in case of conflicting widths, sort those envelopes by height in descending order.

2. Initialize an empty array, lis, to store the heights of envelopes in increasing order. It will track the envelopes based on height.

3. For each envelope’s width and height:

   1. Use the helper function, find_position, to find the correct position to insert a height in lis while maintaining order.

   2. If the position equals the length of lis, append the height to lis as the height can extend the sequence.

   3. Otherwise, replace the height at the position in lis to keep the sequence as small as possible while maintaining the subsequence.

4. After processing all envelopes, the length of the lis gives the maximum number of envelopes that can be Russian dolled.

The helper function, find_position, uses binary search to find the position where the height of the current envelope will be inserted in the lis. It takes the lis array and the height of the current envelope as parameters and performs the following steps:

1. Initialize left and right at the starting and ending indexes of the lis array, respectively.

2. Perform binary search until left exceeds right:

   1. Calculate the midpoint, mid, between left and right.

   2. If the value at mid is smaller than the height, move the left to mid + 1 to search the right half.

   3. Otherwise, adjust the right to mid-1 to search the left half.

3. Finally, the left gives the position where the height can fit.

Let’s look at the following illustration to get a better understanding of the solution: