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. Consider the following Python code snippet implementing the optimal backtracking solution for Expression Add Operators. Given input num = "123" and target = 6, what is the final list of expressions returned by the function?

easy

A. ["1+2+3", "1*2*3"]

B. ["1+2+3", "1*2*3", "12-6"]

C. ["1+2+3", "1*2*3", "1+23"]

D. ["1+2+3", "1*2*3", "1-2+3"]

4. The following code attempts to implement the optimal DP solution for the Best Time to Buy Sell IV problem. Which line contains a subtle bug that can cause incorrect results for large k?

def maxProfit(k, prices):
    n = len(prices)
    if k >= n // 2:
        profit = 0
        for i in range(1, n):
            profit += max(0, prices[i] - prices[i - 1])
        return profit
    next_dp = [[0, 0] for _ in range(k + 1)]
    curr_dp = [[0, 0] for _ in range(k + 1)]
    for i in range(n - 1, -1, -1):
        for t in range(1, k + 1):
            curr_dp[t][0] = max(-prices[i] + next_dp[t][1], next_dp[t][0])
            curr_dp[t][1] = max(prices[i] + next_dp[t - 1][0], next_dp[t][1])
        next_dp, curr_dp = curr_dp, next_dp
    return next_dp[k][0]

medium

A. Line 3: The condition should be k >= n // 2 instead of k > n // 2

B. Line 10: Using next_dp[t][1] instead of next_dp[t-1][1] in curr_dp[t][0] update

C. Line 13: Swapping next_dp and curr_dp incorrectly

D. Line 7: Summing max(0, prices[i] - prices[i - 1]) without checking if prices is empty

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: Trace backtrack calls for num="123", target=6

Step 2: Verify no other expressions equal 6

Final Answer:

Quick Check:

Solution

Step 1: Trace first iteration

Step 2: Trace second iteration

Step 3: Trace third iteration

Final Answer:

Quick Check:

Solution

Step 1: Understand problem constraints

Step 2: Identify efficient pruning technique

Final Answer:

Quick Check:

Solution

Step 1: Analyze the unlimited transactions condition

Step 2: Understand impact of the bug

Final Answer:

Quick Check:

Solution

Step 1: Identify eviction process

Step 2: Confirm no sorting or nested loops

Final Answer:

Quick Check:

Ready to prove it?