Russian Doll Envelopes

Let's explore different approaches to solve the Russian Doll Envelopes problem.

1. Brute Force Approach

• Idea: Try all possible combinations of envelopes and find the longest chain where each envelope fits into the next.

• Algorithm:

  1. Sort the envelopes.
  2. Use recursion to explore all possible chains.
  3. For each envelope, check if it can fit into the previous envelope in the chain.
  4. Keep track of the maximum length of the chain.

• Code (Python):

def maxEnvelopes_brute_force(envelopes):
    envelopes.sort()
    max_count = 0

    def can_fit(env1, env2):
        return env1[0] < env2[0] and env1[1] < env2[1]

    def solve(index, current_chain_length, previous_envelope):
        nonlocal max_count
        max_count = max(max_count, current_chain_length)

        for i in range(index, len(envelopes)):
            if previous_envelope is None or can_fit(previous_envelope, envelopes[i]):
                solve(i + 1, current_chain_length + 1, envelopes[i])

    solve(0, 0, None)
    return max_count

• Time Complexity: O(2ⁿ), where n is the number of envelopes, due to exploring all possible subsets.
• Space Complexity: O(n) due to the recursion depth.

Edge Cases:

• Empty input: Should return 0.
• No envelopes can fit into each other: Should return 1 (each envelope forms a chain of length 1).
• Duplicate envelopes: Should handle them correctly by considering only valid fits.

2. Optimal Solution: Dynamic Programming with Binary Search

• Idea: Sort the envelopes based on width (increasing) and if widths are the same, sort by height (decreasing). This ensures that among envelopes with the same width, only the one with the largest height is considered. Then, find the longest increasing subsequence (LIS) of heights.

• Algorithm:

  1. Sort the envelopes: sort by width ascending, and by height descending if widths are equal.
  2. Extract the heights.
  3. Find the LIS of the heights using binary search.

• Code (Python):

import bisect

def maxEnvelopes(envelopes):
    # Sort by width ascending and height descending if widths are equal
    envelopes.sort(key=lambda x: (x[0], -x[1]))

    heights = [env[1] for env in envelopes]
    tails = []

    for height in heights:
        # If height is greater than all tails, extend the tails list
        if not tails or height > tails[-1]:
            tails.append(height)
        else:
            # Find the smallest tail that is >= height and replace it with height
            index = bisect.bisect_left(tails, height)
            tails[index] = height

    return len(tails)

• Time Complexity: O(n log n), where n is the number of envelopes. The sorting takes O(n log n), and the binary search for LIS takes O(n log n).
• Space Complexity: O(n), due to the tails list which stores the LIS.

Edge Cases:

• Empty input: The tails list will be empty, and the function returns 0, which is correct.
• Envelopes with the same width and height: The sorting ensures that only one of them contributes to the LIS.
• Envelopes that can't fit into any other envelope: The LIS algorithm will find the longest sequence of envelopes that can be Russian-dolled, handling cases where some envelopes are isolated.

Summary

The optimal solution using dynamic programming and binary search provides a much more efficient way to solve the Russian Doll Envelopes problem compared to the brute-force approach. The key is to correctly sort the envelopes and then apply the Longest Increasing Subsequence algorithm.