NUHMAN.com

📘 Problem Statement

You are given a list of envelopes with dimensions [width, height]. One envelope can fit into another if both the width and height of one are strictly smaller than the other.

🔧 Goal: Return the maximum number of envelopes you can nest (Russian doll style).

📥 Example

python

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The sequence [[2,3] => [5,4] => [6,7]] can be nested.

🧠 Approach

This is a 2D version of Longest Increasing Subsequence (LIS).

💡 Key Insight:

1. Sort the envelopes:

• Ascending by width
• If widths are equal, descending by height

1. Extract heights and run LIS on them.

Why sort heights in descending order when widths are equal?

To prevent envelopes with the same width from being nested.

🐍 Python Code (Using Binary Search for LIS)

python

from bisect import bisect_left

class Solution:
    def maxEnvelopes(self, envelopes: list[list[int]]) -> int:
        # Step 1: Sort by width ASC, height DESC
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        # Step 2: Extract the heights
        heights = [h for w, h in envelopes]

        # Step 3: Apply LIS on heights
        lis = []

        for h in heights:
            idx = bisect_left(lis, h)
            if idx == len(lis):
                lis.append(h)
            else:
                lis[idx] = h

        return len(lis)

🔍 Step-by-Step Breakdown

1. Sort envelopes: [(2,3), (5,4), (6,7), (6,4)] → sorted as [(2,3), (5,4), (6,7), (6,4)]

• Note that (6,7) comes before (6,4) due to descending height for same width.

1. Extract heights: [3, 4, 7, 4]
2. Apply LIS:

• 3 → [3]
• 4 → [3, 4]
• 7 → [3, 4, 7]
• 4 → replaces index 1 (4), remains [3, 4, 7]

✅ Final length = 3

⏱️ Time & Space Complexity

OperationComplexitySortingO(n log n)LIS (Binary Search)O(n log n)SpaceO(n)

🧵 Alternate Approach (DP – Slower)

You can use classic DP with O(n²) time, but it's inefficient for large inputs.

🧭 Final Thoughts

This problem elegantly combines:

• Sorting tricks
• Dynamic programming (LIS)
• Binary search (via bisect_left)

It’s an excellent real-world example of combining multiple algorithmic concepts. A must-practice for interview prep!