हिन्दी flagहिन्दी  
CLOSE

Suggested:

🛠️ Settings

Problem Statement

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.

LeetCode:

Constraints:

1 <= envelopes.length <= 10^5
envelopes[i].length == 2
1 <= wi, hi <= 10^5
  • 1 ≤ envelopes.length ← 10^5
    • This means the total number of envelopes is at least 1 and at most 100,000.
    • Your algorithm needs to be efficient, the brute force solutions or nested loops will give the TLE, like O(n^2) for 10^5 will computes to 10^10, which would give TLE.
    • So a efficient solution ideally O(n log n) should be used.
  • envelopes[i].length == 2
    • Each envelope has the length of 2.
  • 1 <= wi, hi <= 10^5
    • The range for the width (wi) and height (hi) is in the range of 1 to 100,000.

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

Different Approaches

1️⃣ Recursion (Brute Force Approach, TLE)

Intuition:

This approach involves checking each pair of envelopers and determining if one can fit inside the other. For each envelope, check all previous envelopers to see if it can be nested inside them.

Approach:

This is the simplest approach. We check every pair of envelopes to see if one can fit inside the other. If an envelope can fit inside another, we increment the sequence length. This is done for all possible pairs.

  1. Sort the envelopes by width and height.
  2. For each envelope, check all previous envelopes to see if they can be nested inside the current envelope.

Code:

class Solution {
public:
    // Recursive helper function to find the maximum number of envelopes that can be nested
    // index: current envelope index
    // prevIndex: previous envelope index, -1 means there's no previous envelope
    int solve(int index, int prevIndex, vector<vector<int>>& envelopes) {
        // Base case: If index reaches the end of the envelopes, no more envelopes to process
        if (index == envelopes.size()) {
            return 0;
        }

        // Variable to store the result of taking the current envelope
        int take = 0;
        
        // If prevIndex is -1, it means we're considering the first envelope,
        // or if current envelope can fit inside the previous envelope
        if (prevIndex == -1 || (envelopes[index][0] > envelopes[prevIndex][0] && envelopes[index][1] > envelopes[prevIndex][1])) {
            // Take the current envelope and continue solving for the next index, 
            // updating the previous index to the current one
            take = 1 + solve(index + 1, index, envelopes);
        }

        // Variable to store the result of skipping the current envelope
        int skip = solve(index + 1, prevIndex, envelopes);
        
        // Return the maximum of taking or skipping the current envelope
        return max(take, skip);
    }

    // Main function to start the process
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        // Sort envelopes by width, and by height if widths are equal
        // Sorting helps ensure that when we compare envelopes, they are in the correct order
        sort(envelopes.begin(), envelopes.end());

        int n = envelopes.size();

        // Start the recursive function with index 0 and no previous envelope (-1)
        return solve(0, -1, envelopes);
    }
};

Complexity Analysis:

  • Time Complexity: O(2^n)
    • Sorting: O(n log n) for sorting the envelope based on the width.
    • Recursion: The recursion explores two options at each step (take or skip), leading to a time complexity of O(2^n).
  • Space Complexity: O(n)
    • Recursion Depth: The recursion depth will be at most O(n), since we are going through each envelope once.

2️⃣ Memoization

Code:

class Solution {
public:
    int solve(int index, int prevIndex, vector<vector<int>>& envelopes, vector<vector<int>>& dp) {
        // Base case: if we have checked all envelopes, return 0
        if (index == envelopes.size()) {
            return 0;
        }

        // If the result for this subproblem is already computed, return it
        if (dp[index][prevIndex + 1] != -1) {
            return dp[index][prevIndex + 1];
        }

        // Option 1: Take the current envelope if it's valid to add (nested inside the prevIndex envelope)
        int take = 0;
        if (prevIndex == -1 || (envelopes[index][0] > envelopes[prevIndex][0] && envelopes[index][1] > envelopes[prevIndex][1])) {
            take = 1 + solve(index + 1, index, envelopes, dp); // Include this envelope and move to next index
        }

        // Option 2: Skip the current envelope and move to the next one
        int skip = solve(index + 1, prevIndex, envelopes, dp);

        // Memoize the result for the current subproblem
        return dp[index][prevIndex + 1] = max(take, skip); // Return the maximum of both options
    }

    int maxEnvelopes(vector<vector<int>>& envelopes) {
        // Sort envelopes: first by width (ascending), and then by height (descending)
        sort(envelopes.begin(), envelopes.end());

        int n = envelopes.size();
        // Initialize dp table with -1 indicating uncomputed states
        vector<vector<int>> dp(n, vector<int>(n + 1, -1));

        // Start the recursive call with index 0 and no previous envelope (-1)
        return solve(0, -1, envelopes, dp);
    }
};

Complexity Analysis:

  • Time Complexity: O(n^2)
    • Sorting the envelopes takes O(n log n)
    • The solve function uses recursion with memoization.
      • Each subproblem is solved only once, and there are O(n^2) subproblems, leading to a time complexity of O(n^2)
    • Overall Time Complexity: O(n^2)
  • Space Complexity: O(n^2)
    • The dp table has size O(n^2), and the recursion stack depth is O(n).

3️⃣ Tabulation (Bottom-Up Approach)

Code:

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        // Step 1: Sort envelopes
        // Sort by width in ascending order
        // If two envelopes have the same width, sort by height in **descending** order
        // This prevents envelopes with the same width from being incorrectly nested
        sort(envelopes.begin(), envelopes.end(), [](vector<int>& first, vector<int>& second) {
            if (first[0] != second[0]) {
                return first[0] < second[0]; // Ascending width
            } else {
                return first[1] > second[1]; // Descending height for same width
            }
        });

        int n = envelopes.size();

        // Step 2: Apply LIS on the height of envelopes
        // dp[i] stores the length of the longest sequence ending at envelope i
        vector<int> dp(n, 1); // Initialize all LIS lengths to 1

        int maxi = 1; // Stores the max length of LIS found so far

        // Classic O(n^2) LIS
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // If current envelope can fit into this one (only check height since width already handled)
                if (envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            // Update global maximum
            maxi = max(dp[i], maxi);
        }

        return maxi; // Return the max number of envelopes that can be nested
    }
};

Complexity Analysis:

  • Time Complexity: O(n^2)
    • Sorting: O(n log n)
    • LIS using DP:
      • Outer loop runs n times, inner loop runs up to n times - O(n^2)
  • Space Complexity: O(n)
    • dp array of size n

4️⃣ Patience Sorting

Intuition:

When solving problems that involve two dimensions, a powerful technique is to reduce the problem from 2D to 1D. This simplification often allows us to apply classic algorithms like Longest Increasing Subsequence (LIS), drastically improving the time complexity from quadratic to logarithmic levels.

A key idea to unlock this transformation is:

Sort first when things are undecided.

Sorting makes the data more structured and less chaotic, allowing us to reason about it more clearly. In many problems, sorting isn't just a preprocessing step—it becomes the foundation upon which the entire logic is built.

This is exactly the case with the Russian Doll Envelopes problem. Once we sort the envelopes correctly, the problem reduces to a well-known 1D problem: finding the LIS of heights.

But this raises an important question:

What Is the Correct Sorting?

The "correct" sorting depends on the problem constraints. For the Russian Doll Envelopes problem, we need:

  • To nest envelopes, both width and height must increase.
  • But two envelopes with the same width can’t be nested even if one has a smaller height.

So, the correct sorting is:

  1. Sort by width in ascending order.
  2. If widths are equal, sort by height in descending order.

This prevents two envelopes with the same width from being part of the same increasing subsequence (because we can’t nest them). Sorting heights in descending order for equal widths ensures they don’t interfere with the LIS that follows.

Once the envelopes are sorted this way, we can safely ignore the widths and focus only on finding the LIS of the heights. Why?

Because:

  • Widths are already strictly increasing (or non-conflicting due to descending sort of heights).
  • If we find the longest increasing sequence of heights, we can be sure the widths are compatible due to sorting.

So we have transformed a 2D nesting problem into a classic 1D LIS problem.

Code:

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        // Step 1: Sort envelopes by width ascending and height descending
        sort(envelopes.begin(), envelopes.end(), [](vector<int>& first, vector<int>& second) {
            if (first[0] != second[0]) return first[0] < second[0];
            return first[1] > second[1]; // For same width, sort by height in descending order
        });

        vector<int> piles;
        for (auto& envelope : envelopes) {
            int height = envelope[1];
            // Perform binary search to find the correct position to insert the height
            auto it = lower_bound(piles.begin(), piles.end(), height);
            if (it == piles.end()) {
                piles.push_back(height); // Create a new pile
            } else {
                *it = height; // Replace the top of the pile with the smaller height
            }
        }

        return piles.size();
    }
};

Complexity Analysis:

  • Time Complexity: O(n log n)
    • Sorting: O(n log n)
    • Patience Sorting (LIS construction): O(n log n)
  • Space Complexity: O(n)
Your experience on this site will be improved by allowing cookies Cookie Policy