Russian Doll Envelopes
Last Updated: 15 Jan, 2021
Difficulty: Hard
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
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
Approach 1
- 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.
Approach 2
Sort all the envelopes according to their height in non-decreasing order and if the height of envelopes is the same then arrange them in non-increasing order of their width. The maximum number of envelopes you can Russian doll will now be the length of the Longest Increasing Subsequence of widths.
This is because after sorting all heights will increase, so we only need to consider widths.
Note, we arrange width in decreasing order when the height is the same, this prevents Longest increasing subsequence algorithm, to include more than one envelope with the same height.
For example if there are 4 envelopes [2,3], [4,6], [3,7], [4,8] in [height, width] manner.
Then after sorting by height we get, [2, 3], [3, 7], [4, 8], [4, 6].
Now, we only consider the widths. The order of widths will be the one obtained after sorting by height. The maximum number of envelopes you can Russian Doll is the length of the longest increasing subsequence of [3, 7, 8, 6] that is 3.
We can implement it as follows.
- Make an integer matrix ‘envelopes’ of dimension (n, 2).
- Run a loop where ‘i’ ranges from 0 to n-1 and for each ‘i’ assign ‘envelopes[i][0]’:= ‘height[i]’ and ‘envelopes[i][1]’ := ‘width[i]’.
- Sort the matrix ‘boxes’ in non-decreasing order of height. If the heights of two boxes are the same, then place them in non-increasing order of width.
- The maximum number of boxes that you can Russian Doll will now be the length of the Longest Increasing Subsequence of widths i.e second column of matrix ‘envelopes’ after sorting.
- Make an integer array ‘maxEnvelopes’ of size ‘n’, where ‘maxEnvelopes[i]’ will give the maximum number of envelopes that can Russian doll if the ‘ith’ envelope after sorting is the outermost envelope.
- Initialize an integer variable ‘result’:= 0, it will keep track of the maximum possible number of envelopes that can Russian doll.
- Run a loop where ‘i’ ranges from 0 to n-1 and for each ‘i’ perform the following steps-:
- Assign ‘maxEnvelopes[i]’ := 1.
- Run a loop where j ranges from 0 to i-1. If ‘envelopes[j][1]’ is strictly less than envelopes[i][1], then update ‘maxEnvelopes[i]’ with the maximum of its current value and sum of ‘maxEnvelopes[j]’ + 1.
- Update ‘result’ with the maximum of its current value and ‘maxEnvelopes[j]’.
- Return ‘result’
Approach 3
As explained in the previous approach this problem will reduce to finding the Longest Increasing Subsequence. We can also find the Longest Increasing Subsequence in O(N * log(N)) using dynamic programming and binary search as explained here.
We can implement it as follows.
- Make an integer matrix ‘envelopes’ of dimension (N, 2).
- Run a loop where ‘i’ ranges from 0 to N - 1 and for each ‘i’ assign ‘envelopes[i][0]’:= ‘height[i]’ and ‘envelopes[i][1]’ := ‘width[i]’.
- Sort the matrix ‘boxes’ in non-decreasing order of height. If the heights of two boxes are the same, then place them in non-increasing order of width.
- The maximum number of boxes that you can Russian Doll will now be the length of the Longest Increasing Subsequence of widths i.e second column of matrix ‘envelopes’.
- Make an integer array ‘arr’ of size ‘N’. and copy the second column of matrix ‘envelopes’ after sorting in array temp by preserving order.
Return length of the longest increasing subsequence of array ‘arr’. We can find it efficiently using dynamic programming and binary search as explained here.
SIMILAR PROBLEMS
Ninja And The Strictly Increasing Array
Posted: 27 Nov, 2022
Difficulty: Moderate
Negative To The End
Posted: 16 Dec, 2022
Difficulty: Easy
8-Queen Problem
Posted: 19 Dec, 2022
Difficulty: Easy
Day 28 : Fake Coin Problem
Posted: 24 Dec, 2022
Difficulty: Easy
Find Duplicate in Array
Posted: 5 Jun, 2023
Difficulty: Easy
