Russian Doll Envelopes

Try to solve the Russian Doll Envelopes problem.

We'll cover the following

Statement

You are given a 2D array of integers, envelopes, where each element envelopes[i] = [wi, hi] represents the width and height of an envelope. An envelope can fit inside another if and only if its width and height are strictly smaller than the width and height of the other envelope. The task is to determine the maximum number of envelopes that can be nested inside each other, similar to Russian dollsRussian dolls, also known as stacking dolls or nesting dolls, are a set of wooden dolls of decreasing size placed one inside another. .

Constraints:

  • 1≤1\leq envelopes.length ≤103\leq 10^3

  • envelopes[i].length ==2== 2

  • 1≤1\leq wi, hi ≤104\leq 10^4

Examples

Press + to interact
canvasAnimation-image
1 of 3

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the problem correctly:

Russian Doll Envelopes

1

How many envelopes can be nested into each other in the following input?

envelopes = [[3,1],[3,6],[2,1],[5,5],[4,7]][[3,1],[3,6],[2,1],[5,5],[4,7]]

A)

22

B)

33

C)

44

D)

55

Question 1 of 30 attempted

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to better understand how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Try it yourself

Implement your solution in the following coding playground.

Press + to interact
Java
usercode > Solution.java
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
      
        // Replace this placeholder return statement with your code
        return -1;
    }
}
Russian Doll Envelopes

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.