Russian Doll Envelopes

The problem of finding the maximum number of envelopes you can Russian doll is a more complicated version of the classic Longest Increasing Subsequence (LIS) problem.

Here’s how to approach the problem:

  1. Sort the Envelopes: Sort the envelopes by width in ascending order. If two envelopes have the same width, sort them by height in descending order. This ensures that when comparing envelopes with the same width, the one with larger height will not be chosen, as it cannot fit inside another envelope with the same width.

  2. Find the Longest Increasing Subsequence: After sorting, the problem is reduced to finding the LIS of the heights.

Below is the code implementing these steps:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

from bisect import bisect_left

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        # Sort the envelopes by width (ascending) and height (descending for the same width)
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        # Apply the logic to find Longest Increasing Subsequence (LIS) on heights
        heights = [x[1] for x in envelopes]
        LIS = []
        for height in heights:
            pos = bisect_left(LIS, height)
            if pos == len(LIS):
                LIS.append(height)
            else:
                LIS[pos] = height

        return len(LIS)

Explanation:

  • The sort method arranges the envelopes so that you can apply the LIS algorithm to the heights.
  • The bisect_left function from the bisect module is used to find the position at which a height can be inserted in the LIS array. If the height can extend the current LIS, it is appended; otherwise, it replaces an existing element.
  • The length of the LIS array gives you the maximum number of envelopes you can Russian doll.

The time complexity of this approach is (O(N \log N)), where (N) is the number of envelopes.

from bisect import bisect_left

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def maxEnvelopes(self, arr: List[List[int]]) -> int:
        # sort increasing in first dimension and decreasing on second
        arr.sort(key=lambda x: (x[0], -x[1]))

        def lis(nums):
            dp = []
            for i in range(len(nums)):
                idx = bisect_left(dp, nums[i])
                if idx == len(dp):
                    dp.append(nums[i])
                else:
                    dp[idx] = nums[i]
            return len(dp)
        # extract the second dimension and run the LIS
        return lis([i[1] for i in arr])

Identifying Problem Isomorphism

“Russian Doll Envelopes” asks for the maximum number of envelopes you can Russian doll, meaning to put one inside another, based on width and height.

An isomorphic problem to this is “Box Stacking” (not directly on LeetCode but a common problem in the category of dynamic programming). This problem asks you to find the highest possible stack of boxes such that for every box, all boxes below it have a larger width, height, and depth.

The reason these problems map to each other is that both involve finding the longest increasing subsequence in a 2D space (width and height in the envelopes problem, width, height, and depth in the box stacking problem).

“Box Stacking” is more complex than “Russian Doll Envelopes”. While the “Russian Doll Envelopes” problem involves finding the maximum number of envelopes that can be put into another based on two dimensions, “Box Stacking” involves the additional dimension of depth.

“Russian Doll Envelopes” is simpler as it involves only two dimensions (width and height) and requires only two types of comparisons (whether one envelope’s width and height are both smaller than the other’s). On the other hand, “Box Stacking” involves three dimensions (width, height, and depth), making it more complex due to the additional type of comparison needed.

If there were multiple isomorphic problems, “Russian Doll Envelopes” would be the simpler one, followed by “Box Stacking”.

“Box Stacking” is not listed on LeetCode, but it is a common dynamic programming problem that asks for finding the highest possible stack of boxes such that for every box, all boxes below it have a larger width, height, and depth.

An isomorphic problem to “Box Stacking” on LeetCode is “Maximum Length of Pair Chain” (#646). In this problem, you’re given n pairs where the first element of every pair is strictly less than the second element, and you need to find the longest chain which can be formed such that for every pair (i, j) in the chain, i < j.

The reason for this mapping is that both problems involve finding the longest sequence based on a certain condition. In “Box Stacking”, the condition is that the width, height, and depth of each box in the stack must be smaller than the box beneath it. In “Maximum Length of Pair Chain”, the condition is that the first element of each pair must be smaller than the second element of the preceding pair.

“Box Stacking” is more complex than “Maximum Length of Pair Chain”. This is because “Box Stacking” requires dealing with three dimensions (width, height, and depth), whereas “Maximum Length of Pair Chain” only involves pairs (two dimensions).

If there were multiple isomorphic problems, “Maximum Length of Pair Chain” would be the simpler one, followed by “Box Stacking”.

10 Prerequisite LeetCode Problems

“354. Russian Doll Envelopes” is a problem of sorting and dynamic programming. Here are 10 problems to build up the skills needed for solving this problem:

  1. “300. Longest Increasing Subsequence”

    • This problem is crucial as “Russian Doll Envelopes” is essentially a variant of this problem. The primary difference is that you have an extra dimension to consider.

  2. “198. House Robber”

    • This problem also uses dynamic programming and helps you think about optimal sequences.

  3. “673. Number of Longest Increasing Subsequence”

    • This problem is a good continuation after the “Longest Increasing Subsequence”. It includes the same concepts, but adds some additional complexity.

  4. “646. Maximum Length of Pair Chain”

    • This problem is very similar to “Russian Doll Envelopes”, but a bit easier. It’s a good problem to solve before tackling the main one.

  5. “70. Climbing Stairs”

    • This is a basic dynamic programming problem and can help you understand the basics of this type of problem.

  6. “322. Coin Change”

    • Another classic dynamic programming problem. It will help you get comfortable with this type of problem.

  7. “215. Kth Largest Element in an Array”

    • This problem can help you understand sorting and its importance in simplifying problems.

  8. “34. Find First and Last Position of Element in Sorted Array”

    • Understanding how to handle sorted arrays is a key to solving the “Russian Doll Envelopes” problem.

  9. “128. Longest Consecutive Sequence”

    • This problem is another one that revolves around ordering and sequence.

  10. “435. Non-overlapping Intervals”

    • Understanding how to handle and compare intervals is important in the “Russian Doll Envelopes” problem.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes.sort(key=lambda x: (x[0], -x[1]))        
        res = []
        for _, h in envelopes:
            idx = bisect_left(res, h)
            if idx == len(res):
                res.append(h)
            else:
                res[idx]=h
        return len(res)

Problem Classification

The task is to find the maximum number of envelopes that can be put one inside another. This is a Nested Object Maximization Problem.

Language Agnostic Coding Drills

The code is implementing a variant of the Longest Increasing Subsequence (LIS) problem. It first sorts the ’envelopes’ list and then uses a binary search algorithm to find the longest subsequence. Here are the key concepts involved in solving this problem:

  1. Sorting a List of Lists: The first concept you need to understand is how to sort a list of lists. In this problem, you’re not just sorting based on the first element of each sub-list but also considering the second element.

  2. Sorting with a Custom Comparator: This builds upon the previous concept but introduces the idea of a custom sorting function. In Python, you can pass a lambda function as the ‘key’ argument to the sort function to control how the list is sorted.

  3. Understanding the Longest Increasing Subsequence (LIS) Problem: This is a well-known problem in computer science, and understanding it is key to understanding the code above. The problem asks for the length of the longest subsequence of a given sequence in which the subsequence’s elements are in sorted order.

  4. Solving the LIS Problem with Dynamic Programming: A common approach to solving the LIS problem is to use dynamic programming, a method for solving problems by breaking them down into smaller, simpler sub-problems and combining their solutions to solve the larger, original problem.

  5. Solving the LIS Problem with Binary Search: An alternative approach to solving the LIS problem is to use binary search. This approach involves maintaining an active list of potential subsequences and using binary search to update the list as you iterate through the input sequence. This method tends to be more efficient than the dynamic programming approach.

  6. Understanding the bisect_left Function: The bisect_left function is a powerful tool in Python for performing binary searches. Understanding how it works and when to use it is key to understanding the code above.

  7. Applying the LIS Problem to the ‘Max Envelopes’ Problem: The final step is to understand how the LIS problem applies to the ‘Max Envelopes’ problem. Once you understand the LIS problem and how to solve it, it’s a matter of translating the envelopes into a sequence of numbers and applying the LIS algorithm.

Targeted Drills in Python

Let’s write code snippets for each concept to understand how they work:

  1. Sorting a List of Lists:
1
2
3
4

# This will sort each sublist by its first element
lists = [[2, 3], [1, 5], [3, 2]]
lists.sort()
print(lists)  # Output: [[1, 5], [2, 3], [3, 2]]
  1. Sorting with a Custom Comparator:
1
2
3
4

# Sorts based on first element of each sublist, then by second element in reverse order
lists = [[2, 3], [1, 5], [2, 2], [1, 6]]
lists.sort(key=lambda x: (x[0], -x[1]))
print(lists)  # Output: [[1, 6], [1, 5], [2, 3], [2, 2]]

  1. Understanding the Longest Increasing Subsequence (LIS) Problem:

    • This concept is better understood theoretically, so no Python code here.

  2. Solving the LIS Problem with Dynamic Programming:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def length_of_LIS(nums):
    if not nums:
        return 0

    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)
  1. Solving the LIS Problem with Binary Search:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from bisect import bisect_left

def length_of_LIS(nums):
    dp = []
    for num in nums:
        idx = bisect_left(dp, num)
        if idx == len(dp):
            dp.append(num)
        else:
            dp[idx] = num
    return len(dp)
  1. Understanding the bisect_left Function:
1
2
3
4

from bisect import bisect_left

nums = [1, 2, 4, 5]
print(bisect_left(nums, 3))  # Output: 2 (3 should be placed at index 2 to maintain sorted order)
  1. Applying the LIS Problem to the ‘Max Envelopes’ Problem:
    • This is your final solution, so this will be applying all the above drills together:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from bisect import bisect_left

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        dp = []
        for _, h in envelopes:
            idx = bisect_left(dp, h)
            if idx == len(dp):
                dp.append(h)
            else:
                dp[idx] = h
        return len(dp)