Russian Doll Envelopes

Hard
0/120
Average time to solve is 50m
profile
Contributed by
20 upvotes
Asked in companies
UberFacebookHSBC

Problem statement

You are given a set of ‘N’ rectangular envelopes. The height and width of each envelope are given by arrays, ‘height’ and ‘width’ respectively, each consisting of ‘N’ positive integers. The height, width of the ith envelope is given by ‘height[i]’ and ‘width[i]’ respectively.

You can put one envelope inside another envelope if and only if both the height and width of one envelope is strictly greater than the height and width of the other envelope.

What is the maximum number of envelopes you can Russian doll? (put one inside other)

Note 
Rotation of envelope is not allowed, that is, height and width can’t be exchanged
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The next 3*T lines represent the ‘T’ test cases.

The first line of each test case contains an integer ‘N’, representing the number of envelopes.

The second line of the test case contains ‘N’ space-separated integers representing elements of the array ‘height’.

The third line of the test case contains ‘N’ space-separated integers representing elements of the array ‘width’.
Output Format : 
For each test case, print, in a separate line, the maximum number of envelopes you can Russian doll.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 50
1 <= n <= 10^4
1 <= height[i] <= 10^9
1 <= width[i] <= 10^9

Time Limit: 2 sec
Sample Input 1:
2
4
5 6 6 2
4 4 7 3
2
2 1 
2 1
Sample Output 1:
3 
2
Explanation For Sample Output 1:
Test Case 1:
The number envelopes, ‘N’ = 4 
‘height’ = {5, 6, 6, 2}
‘width’= {4, 4, 7, 3}
Let denote dimensions of the envelope in (Height, Width) manner then, one way of Russian Doll envelopes in outermost to the innermost manner is as follow:

Select the third envelope, i.e., envelope with dimensions (6, 7) as the outermost envelope.

Place the first envelope i.e envelope with dimensions (5, 4) inside the outermost envelope. You can do this because both the height and width of this envelope is strictly less than the outermost envelope.

Place the fourth envelope i.e envelope with dimensions (2, 3) inside the previous envelope.

In this way, we can Russian Doll 3 envelopes. 

No other way can Russian Doll more than 3 envelopes.

Test Case 2:
You can put the second envelope inside the first envelope because both the height and width of the second envelope are strictly less than the first envelope.
Sample Input 2:
 2
 1
 2
 3
 3
 1 1 1
 1 1 1
Sample Output 2:
 1
 1
Hint

Try out all the possible ways to Rusian Doll envelopes.

Approaches (3)
Brute Force
  • This is a recursive approach.
  • Initialize two integer variables ‘maxHeight’:= INF,  ‘maxWidth’ := INF, where INF denotes infinity. These variables will keep the maximum height and width of the envelope that can be placed inside.
  • Recursively try out all possible ways of Russian doll envelopes and find out the maximum number of the envelopes that can Russian Doll. This can be done by performing the following step in each recursive call -:
    • Initialize an integer variable ‘maxEnvelope’ := 0.
    • Iterate over all ‘n’ envelopes in each recursive call and if the width of the envelope is strictly less than ‘maxWidth’ and the height of the envelope is strictly less than ‘maxHeight’ then try to place this envelope inside by making a recursive call with ‘maxWidth’ and ‘maxHeight’  as width and height of current envelope respectively. Update value of ‘maxEnvelope’ with a maximum of its current value and 1 + value returned in that recursive call.
    • Return ‘maxEnvelope’.
  • Return the value obtained by recursive function, It will be the maximum number of envelopes that can Russian Doll.
Time Complexity

O(N!), where  ‘N’ is the number of envelopes.

 

In the worst case, the first call to a recursive function can make ‘N’ successive recursive calls,  Each of which can further make ‘N - 1’ recursive calls and so on.

Space Complexity

O(N), where  ‘N’ is the number of envelopes.

 

The size of the implicit stack involved in recursion will be of the order of ‘N’.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Russian Doll Envelopes
Full screen
Console