What happens if you sorting both width and height ascending?

Incorrect counting of envelopes with same width but different heights, leading to wrong answer Fix: Sort width ascending and height descending to avoid counting envelopes with same width multiple times

What happens if you using lis on widths instead of heights after sorting?

Incorrect subsequence calculation, as width is already sorted and may not reflect nesting Fix: Apply LIS on heights after sorting envelopes by width

What happens if you using <= instead of < in comparisons?

Allows envelopes with equal width or height to nest, violating problem constraints Fix: Use strictly less than (<) for both width and height comparisons

What happens if you not handling empty input?

Code may crash or return incorrect result Fix: Check for empty envelopes list and return 0

Interview Prepchallenge-problemshardGoogleAmazon

Russian Doll Envelopes

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

hardMIXEDGoogleAmazon

Imagine you have a collection of envelopes of different sizes, and you want to nest them inside each other like Russian dolls to save space.

💡 This problem is about finding the longest sequence of envelopes where each envelope can fit inside the next one. Beginners often struggle because it combines sorting with a complex subsequence problem, requiring careful ordering and optimization.

📋

Problem Statement

Given a list of envelopes with widths and heights, find the maximum number of envelopes you can nest inside each other. An envelope can fit into another if and only if both the width and height of one envelope are strictly less than those of the other. Input: an array of envelopes where each envelope is represented as [width, height]. Output: an integer representing the maximum number of envelopes that can be nested.

1 ≤ n ≤ 10^51 ≤ width, height ≤ 10^9

💡

Example

Input"[[5,4],[6,4],[6,7],[2,3]]"

Output3

The sequence [2,3] fits into [5,4], which fits into [6,7].

All envelopes have the same width and height → output 1
Envelopes sorted in descending order → output 1
Only one envelope → output 1
Envelopes with increasing width but same height → output 1

⚠️

Common Mistakes

Sorting both width and height ascending

Incorrect counting of envelopes with same width but different heights, leading to wrong answer

✅ Sort width ascending and height descending to avoid counting envelopes with same width multiple times

Using LIS on widths instead of heights after sorting

Incorrect subsequence calculation, as width is already sorted and may not reflect nesting

✅ Apply LIS on heights after sorting envelopes by width

Using <= instead of < in comparisons

Allows envelopes with equal width or height to nest, violating problem constraints

✅ Use strictly less than (<) for both width and height comparisons

Not handling empty input

Code may crash or return incorrect result

✅ Check for empty envelopes list and return 0

Using linear search instead of binary search in LIS

Solution becomes O(n²) and times out on large inputs

✅ Use binary search to find position in tails array for LIS

🧠

Brute Force (Nested Loops, O(n²))

💡 Starting with brute force helps understand the problem's core: checking all pairs to find the longest nesting sequence. It’s slow but conceptually straightforward.

Intuition

Try every envelope as a potential start and check all envelopes that can fit inside it, building sequences recursively or iteratively.

Algorithm

Sort envelopes by width and height to have a consistent order.
For each envelope, check all previous envelopes to see if it can fit inside.
Use a DP array where dp[i] stores the max nesting ending at envelope i.
Return the maximum value in dp as the answer.

💡 The nested loops and dp array are hard to visualize at first because you must compare pairs and track sequences simultaneously.

</>

Code

from typing import List

def maxEnvelopes(envelopes: List[List[int]]) -> int:
    envelopes.sort(key=lambda x: (x[0], x[1]))
    n = len(envelopes)
    dp = [1] * n
    for i in range(n):
        for j in range(i):
            if envelopes[j][0] < envelopes[i][0] and envelopes[j][1] < envelopes[i][1]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp) if dp else 0

# Driver code
if __name__ == '__main__':
    test = [[5,4],[6,4],[6,7],[2,3]]
    print(maxEnvelopes(test))

Line Notes

envelopes.sort(key=lambda x: (x[0], x[1]))Sort envelopes to ensure a consistent order for comparison, so we can build sequences in order

dp = [1] * nInitialize dp with 1 since each envelope can at least hold itself as a sequence of length 1

for i in range(n):Outer loop picks the current envelope to build sequences ending here

if envelopes[j][0] < envelopes[i][0] and envelopes[j][1] < envelopes[i][1]Check if envelope j can fit inside envelope i to extend the sequence

import java.util.*;

public class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            else return a[1] - b[1];
        });
        int n = envelopes.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] test = {{5,4},{6,4},{6,7},{2,3}};
        System.out.println(sol.maxEnvelopes(test));
    }
}

Line Notes

Arrays.sort(envelopes, (a, b) -> {Sort envelopes by width then height for consistent ordering to build sequences

int[] dp = new int[n];DP array to store max nesting ending at each envelope

for (int i = 0; i < n; i++) {Outer loop selects current envelope to build sequences

if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {Check if envelope j fits inside envelope i to extend sequence

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxEnvelopes(vector<vector<int>>& envelopes) {
    sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>& b) {
        if (a[0] != b[0]) return a[0] < b[0];
        return a[1] < b[1];
    });
    int n = envelopes.size();
    vector<int> dp(n, 1);
    int max_len = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        max_len = max(max_len, dp[i]);
    }
    return max_len;
}

int main() {
    vector<vector<int>> test = {{5,4},{6,4},{6,7},{2,3}};
    cout << maxEnvelopes(test) << endl;
    return 0;
}

Line Notes

sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>& b) {Sort envelopes by width then height for consistent order to build sequences

vector<int> dp(n, 1);Initialize dp with 1 for each envelope as minimal sequence length

for (int i = 0; i < n; i++) {Outer loop picks current envelope to build sequences

if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {Check if envelope j fits inside envelope i to extend sequence

var maxEnvelopes = function(envelopes) {
    envelopes.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    const n = envelopes.length;
    const dp = new Array(n).fill(1);
    let maxLen = 1;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
};

// Test
console.log(maxEnvelopes([[5,4],[6,4],[6,7],[2,3]]));

Line Notes

envelopes.sort((a, b) => a[0] - b[0] || a[1] - b[1]);Sort envelopes by width then height for consistent order to build sequences

const dp = new Array(n).fill(1);Initialize dp array with 1 for each envelope as minimal sequence length

for (let i = 0; i < n; i++) {Outer loop selects current envelope to build sequences

if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {Check if envelope j fits inside envelope i to extend sequence

⏱

Complexity

TimeO(n²)

SpaceO(n)

Two nested loops over n envelopes lead to O(n²) time. DP array uses O(n) space.

💡 For n=20, this means about 400 comparisons, which is manageable but grows quickly for large n.

Interview Verdict: TLE for large inputs

This approach is too slow for large inputs but helps understand the problem and DP formulation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n²)`	`O(n)`	No	Yes	Mention only - never code
2. Sorting + LIS O(n²)	`O(n²)`	`O(n)`	No	Yes	Mention as improvement, not optimal
3. Sorting + LIS with Binary Search O(n log n)	`O(n log n)`	`O(n)`	No	Yes, with extra tracking	Code this approach

Practice

(1/5)

1. What is the time complexity of the optimal bottom-up DFS solution for computing the diameter of a binary tree with n nodes?

medium

A. O(n) because each node is visited once in the DFS traversal

B. O(n^2) due to repeated height computations in recursion

C. O(n log n) because height computations take log n time per node

D. O(n) but with additional O(n) space for memoization arrays

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Identify that naive recursive approach causes repeated height computations

Step 2: Confirm that optimal bottom-up DFS avoids repeated computations

Step 3: Since O(n) because each node is visited once in the DFS traversal states optimal O(n), but O(n^2) due to repeated height computations in recursion states O(n^2) due to repeated computations, and question asks for optimal solution, correct answer is A.

Final Answer:

Quick Check:

Solution

Step 1: Understand diameter update logic

Step 2: Identify incorrect update using max(left_height, right_height)

Final Answer:

Quick Check:

Solution

Step 1: Identify outer loop complexity

Step 2: Identify inner operation complexity

Final Answer:

Quick Check:

Solution

Step 1: Understand the uniqueness constraint removal

Step 2: Simplify counting approach

Step 3: Why other options fail

Final Answer:

Quick Check:

Solution

Step 1: Understand cycle implications

Step 2: Identify safe approach

Final Answer:

Quick Check:

Ready to prove it?