354. Russian Doll Envelopes


Problem Description

In this problem, we are given a list of envelopes, each with its width and height represented as a pair of integers in a 2D array. The primary goal is to figure out how many unique envelopes can be nested inside one another, one at a time, in what's known as a Russian doll fashion. An envelope can only fit into another one if both its width and height are strictly smaller than those of the envelope it is being fit into. Rotating envelopes is not allowed; we have to consider the width and height in the order they are given. The challenge lies in maximizing the sequence of envelopes that can be nested like this.

Intuition

When we face a problem that asks for the 'maximum number of something', a common approach is to think of it as a dynamic programming problem. However, naive dynamic programming will not be sufficient due to the complexity of nested conditions.

A smarter approach involves sorting and then applying a variation of the longest increasing subsequence (LIS) problem. By sorting the envelopes properly, we ensure that once we are considering an envelope for nesting, all potential outer envelopes have already been considered.

Here are the detailed steps of the intuition and approach:

  1. Sort the envelopes array primarily by width (w) and, in the case where widths are equal, by height (h) in descending order. This might seem counter-intuitive at first because for LIS problems we generally sort in ascending order.
    • The idea behind the custom sorting is that when the widths are the same, sorting heights in descending order ensures that they cannot be placed in the same increasing subsequence, which is essential since we can't nest envelopes with the same width.
  2. We then seek to find the LIS based solely on the heights of our sorted envelopes because we know all widths are increasing in the array due to our sort. So if we find an increasing sequence by height, we have automatically found increasing widths as well.
  3. To implement this using efficient time complexity, we use a binary search with an auxiliary array d (usually termed tails in LIS problems) where we store the last element of the currently known increasing subsequences of various lengths.
  4. Iterating through the sorted envelopes, for each height, we determine where it would fit in our d array:
    • If it's larger than the largest element in d, this height can extend the longest increasing subsequence, so we append it to d.
    • Otherwise, we use binary search to find the smallest element in d that is larger than or equal to the current height, and replace it with the current height, thereby extending the longest increasing subsequence possible at this point (while discarding subsequences that were not the shortest possible).
  5. After processing all envelopes, the length of d represents the length of the longest subsequence of widths and heights that meet the nesting condition, which is the desired result of the problem.

The key insight is that the sorting step simplifies the problem for us, reducing it to an LIS problem that can be solved in (O(N\log N)) time.

Learn more about Binary Search, Dynamic Programming and Sorting patterns.

Solution Approach

The implementation of the solution follows a series of steps which involves sorting, a binary search algorithm, and dynamic programming concepts to efficiently solve the problem.

Firstly, let's discuss the data structure used. The array d plays a crucial role in the implementation. It stores the heights of the envelopes in a way that they form an increasing sequence. This array represents the end elements of the currently known increasing subsequences of varying lengths.

Now, let's walk through each part of the algorithm:

  1. Sort the envelopes array by width in ascending order, and in the case of a tie on the width, sort by height in descending order. This is done using the sort method with a custom lambda function as the key:

    1envelopes.sort(key=lambda x: (x[0], -x[1]))

    Here, x[0] represents the width and x[1] represents the height of each envelope.

  2. Initialize the array d with the height of the first envelope because at least one envelope (the smallest) can be Russian dolled thus far:

    1d = [envelopes[0][1]]
  3. Iterate over the sorted envelopes (ignoring the first one since it's already in d), and apply a binary search to find the correct position of each envelope's height in d:

    1for _, h in envelopes[1:]:
    2    if h > d[-1]:
    3        d.append(h)
    4    else:
    5        idx = bisect_left(d, h)
    6        d[idx] = h
    • We use the bisect_left method from the bisect module in Python, which implements binary search in an efficient manner. The bisect_left function finds the index at which the given height h can be inserted to maintain the ordered sequence.
    • If the height h of the current envelope is greater than the last element in d, it can form a new, longer increasing subsequence by being placed on top of the previous sequence, so it is appended to d.
    • Otherwise, we replace the found position in d with the current height h. This ensures the subsequence remains an increasing one, and we maintain the smallest possible heights in d, which opens up opportunities for future envelopes to be placed in this increasing subsequence.
  4. After processing all envelopes, we return the length of d:

    1return len(d)

    The length of d represents the maximum number of envelopes that can be Russian dolled, because it symbolizes the longest increasing subsequence that we have been able to construct out of the heights while maintaining the sorted order of the widths.

This algorithm is an elegant combination of sorting, dynamic programming, and binary search, resulting in a solution with a time complexity of (O(N\log N)), where (N) is the number of envelopes.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Example Walkthrough

Let’s walk through a small example to illustrate the solution approach outlined above. Suppose we are given the following 2D array of envelopes:

1envelopes = [[5,4],[6,4],[6,7],[2,3]]

This array represents the following envelopes with width and height:

  1. Envelope 1: width=5, height=4
  2. Envelope 2: width=6, height=4
  3. Envelope 3: width=6, height=7
  4. Envelope 4: width=2, height=3

Now, let's apply the steps of the solution approach:

  1. Sort the envelopes array by width in ascending order and by height in descending order within widths:

    After sorting, the envelopes array looks like this:

    1sorted_envelopes = [[2,3],[5,4],[6,7],[6,4]]

    Envelopes with width=6 have been sorted by their heights in descending order.

  2. Initialize the array d with the height of the first envelope:

    1d = [3]
  3. Iterate over the sorted envelopes and apply a binary search to find the correct position of each envelope's height in d:

    • For envelope [5,4]:

      Since the height 4 is greater than the last element in d (3), we append it to d:

      1d = [3,4]
    • For envelope [6,7]:

      Again, the height 7 is greater than the last element in d (4), so we append it:

      1d = [3,4,7]
    • For envelope [6,4]:

      The height 4 is not greater than the last element in d (7). We use binary search to find the correct position of 4 in d, which is at index 1, replacing the element at that position:

      1d = [3,4,7]

      Note that this step maintains the longest increasing subsequence possible and does not change our d in this case because 4 is already present.

  4. After processing all envelopes, we find that the length of d is 3:

    1len(d) = 3

This length indicates that the maximum number of envelopes that can be Russian dolled is 3, corresponding to the following sequence of envelopes: [[2,3], [5,4], [6,7]]. Thus, by applying the smart sorting technique followed by finding the longest increasing subsequence on the heights, we have effectively solved the problem in (O(N\log N)) time.

Solution Implementation

1from bisect import bisect_left
2from typing import List
3
4class Solution:
5    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
6        # Sort the envelopes by width in increasing order and then by height in decreasing order
7        envelopes.sort(key=lambda x: (x[0], -x[1]))
8
9        # Initialize a list to store the increasing heights sequence
10        dp = [envelopes[0][1]]
11
12        # Iterate through the sorted envelopes starting from the second one
13        for _, height in envelopes[1:]:
14            if height > dp[-1]:  # If the current height is greater than the last in dp
15                dp.append(height) # Append it as it forms an increasing sequence
16            else:
17                # Find the index to replace with the current height to keep sequence increasing
18                index = bisect_left(dp, height)
19                # Ensure the index is within range, replace the current height
20                dp[index] = height
21      
22        # The length of dp is the length of the longest increasing subsequence
23        return len(dp)
24
1import java.util.Arrays;
2
3class Solution {
4    public int maxEnvelopes(int[][] envelopes) {
5        // Sort envelopes by width in ascending order; if widths are equal, sort by height in descending order.
6        Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
7      
8        int numEnvelopes = envelopes.length;
9        // 'heights' array stores the heights at which envelopes will end at each position in the subsequence.
10        int[] heights = new int[numEnvelopes + 1];
11        // Initialize the first height in the 'heights' array
12        heights[1] = envelopes[0][1];
13        // 'maxSize' represents the length of the longest increasing subsequence so far.
14        int maxSize = 1;
15      
16        for (int i = 1; i < numEnvelopes; ++i) {
17            int currentHeight = envelopes[i][1];
18            // If the current envelope's height is greater than the last envelope's height in the 'heights' array,
19            // it can be appended to the subsequence.
20            if (currentHeight > heights[maxSize]) {
21                heights[++maxSize] = currentHeight;
22            } else {
23                // Perform binary search to find the correct position to place current envelope's height.
24                int left = 1, right = maxSize;
25                while (left < right) {
26                    int mid = (left + right) >> 1; // Equivalent to (left + right) / 2
27                    if (heights[mid] >= currentHeight) {
28                        right = mid;
29                    } else {
30                        left = mid + 1;
31                    }
32                }
33                // Update the 'heights' array with the current envelope's height at the correct position.
34                int pos = (heights[left] >= currentHeight) ? left : 1;
35                heights[pos] = currentHeight;
36            }
37        }
38        // Return the length of the longest increasing subsequence which corresponds to the maximum number of envelopes.
39        return maxSize;
40    }
41}
42
1class Solution {
2public:
3    int maxEnvelopes(vector<vector<int>>& envelopes) {
4        // Sort envelopes by width; if the same, then by height in decreasing order
5        sort(envelopes.begin(), envelopes.end(), [](const vector<int>& env1, const vector<int>& env2) {
6            return env1[0] < env2[0] || (env1[0] == env2[0] && env1[1] > env2[1]);
7        });
8
9        // Variable to store the number of envelopes
10        int numEnvelopes = envelopes.size();
11
12        // Dynamic Programming vector to store the increasing heights
13        vector<int> heightSequence{ envelopes[0][1] };
14
15        // Process each envelope
16        for (int i = 1; i < numEnvelopes; ++i) {
17            int currentHeight = envelopes[i][1];
18            // If current envelope's height is greater than the last height in the sequence
19            if (currentHeight > heightSequence.back()) {
20                // Add the height to the sequence
21                heightSequence.push_back(currentHeight);
22            } else {
23                // Find the first element in the sequence which is not less than currentHeight
24                auto it = lower_bound(heightSequence.begin(), heightSequence.end(), currentHeight);
25                // Update the sequence element with the currentHeight
26                *it = currentHeight;
27            }
28        }
29        // Return the size of the longest increasing height sequence
30        return heightSequence.size();
31    }
32};
33
1// Function to compare two envelopes; sort by width, then by reverse height if widths are equal
2function compareEnvelopes(env1: number[], env2: number[]): boolean {
3    return env1[0] < env2[0] || (env1[0] === env2[0] && env1[1] > env2[1]);
4}
5
6// Perform a binary search and return the index of the first element in a sorted array
7// which does not compare less than the target height.
8function binarySearch(sequence: number[], targetHeight: number): number {
9    let start = 0;
10    let end = sequence.length - 1;
11    while (start <= end) {
12        let mid = Math.floor((start + end) / 2);
13        if (sequence[mid] < targetHeight) {
14            start = mid + 1;
15        } else {
16            end = mid - 1;
17        }
18    }
19    return start; // The insertion point for the targetHeight
20}
21
22// Envelope sorting and processing to find the maximum envelopes that can be nested
23function maxEnvelopes(envelopes: number[][]): number {
24    // Sort the envelopes based on specified comparison logic
25    envelopes.sort((a, b) => compareEnvelopes(a, b) ? -1 : 1);
26
27    // Initialize the array to store the maximum increasing sequence of heights
28    const heightSequence: number[] = [envelopes[0][1]];
29
30    // Process each envelope starting from the second one
31    for (let i = 1; i < envelopes.length; ++i) {
32        const currentHeight = envelopes[i][1];
33
34        // If the current envelope's height is greater than the last element in the sequence
35        if (currentHeight > heightSequence[heightSequence.length - 1]) {
36            // Append the current height to the sequence
37            heightSequence.push(currentHeight);
38        } else {
39            // Find the index to replace with the current envelope's height
40            const indexToReplace = binarySearch(heightSequence, currentHeight);
41            heightSequence[indexToReplace] = currentHeight;
42        }
43    }
44
45    // Return the length of the longest increasing subsequence of heights
46    return heightSequence.length;
47}
48

Time and Space Complexity

Time Complexity

The time complexity of the maxEnvelopes function is determined by several factors:

  1. Sorting the envelopes requires O(N * log(N)) time, where N is the number of envelopes.
  2. The for loop iterates through the sorted envelopes list, which results in O(N) iterations.
  3. Inside the for loop, a binary search is performed using bisect_left, which takes O(log(N)) time in the worst case for each iteration.

Multiplying the number of iterations (the for loop) by the complexity of each iteration (the binary search) gives us a total for the loop of O(N * log(N)).

Adding the sorting and iteration parts, the final time complexity remains O(N * log(N)), since both have the same asymptotic behavior.

Space Complexity

The space complexity of the function is determined by the storage used for the list d.

  1. The list d is dynamically expanded based on the sequence of heights we can include in the increasing subsequence. In the worst case, d can contain all the heights from the envelopes, which would require O(N) space.
  2. The envelopes list itself takes O(N) space.

Therefore, the overall space complexity is O(N) because it's the largest space requirement.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄