You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Examples

Example 1:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Example 2:

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1
Explanation: No envelope can fit into another envelope.

Constraints

  • 1 <= envelopes.length <= 10^5
  • envelopes[i].length == 2
  • 1 <= wi, hi <= 10^5

Thinking Process

  1. 2D LIS Problem: This is essentially finding LIS in 2D space
  • The search space must shrink monotonically each step.
  • Decide which half still satisfies the predicate, discard the other.
  • Use mid = left + (right - left) / 2 to avoid overflow.
Binary search: shrink [lo … hi] lo mid hi discard half each step → O(log n)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Standard binary search (this problem) O(log n) O(1) Sorted array, left <= right
Lower / upper bound O(log n) O(1) First/last position, insert index
Binary search on rotated array O(log n) O(1) Identify sorted half, discard other
Binary search on answer O(n log M) O(1) Monotonic predicate over search space

Solution

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        if(envelopes.empty()) return 0;
        const int N = envelopes.size();
        sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
            return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
        });

        vector<int> dp = {envelopes[0][1]};
        for(int i = 1; i < N; i++) {
            int num = envelopes[i][1];
            if(num > dp.back()) {
                dp.push_back(num);
            } else {
                auto it = lower_bound(dp.begin(), dp.end(), num);
                *it = num;
            }
        }
        return dp.size();
    }
};

Solution Explanation

Approach: Standard binary search (this problem)

Key idea: 1. 2D LIS Problem: This is essentially finding LIS in 2D space

How the code works:

  1. 2D LIS Problem: This is essentially finding LIS in 2D space
    • The search space must shrink monotonically each step.
    • Decide which half still satisfies the predicate, discard the other.
    • Use mid = left + (right - left) / 2 to avoid overflow.

Walkthrough — input envelopes = [[5,4],[6,4],[6,7],[2,3]], expected output 3:

The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Common Mistakes

  1. Empty input: envelopes = [] → return 0
  2. Single envelope: envelopes = [[1,1]] → return 1
  3. All same size: envelopes = [[1,1],[1,1],[1,1]] → return 1
  4. No valid chain: All envelopes have same width → return 1

  5. Perfect chain: Envelopes form a perfect chain → return n

  6. Wrong sorting order: Not sorting heights descending for equal widths
  7. Using strict inequality: Must use > not >= for fitting condition
  8. Not handling empty input: Should return 0 for empty array
  9. Wrong LIS implementation: Not using binary search optimization
  10. Forgetting equal width constraint: Multiple envelopes with same width can’t be in chain

Key Takeaways

  1. 2D LIS Problem: This is essentially finding LIS in 2D space
  2. Sorting Strategy: Sort by one dimension, then find LIS on the other
  3. Equal Width Handling: Sort heights descending for equal widths to prevent invalid chains
  4. Binary Search Optimization: Use lower_bound for O(log n) insertion
  5. Greedy Approach: Maintain smallest tail elements for each subsequence length

References

Template Reference