Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Problem Statement
2.1.
Example
3.
Recursive Approach
3.1.
Program
3.1.1.
Input
3.1.2.
Output
3.1.3.
Time Complexity
3.1.4.
Space Complexity
4.
Dynamic Programming Approach
4.1.
Program
4.1.1.
Input
4.1.2.
Output
4.1.3.
Time Complexity
4.1.4.
Space Complexity
5.
Key Takeaways
Last Updated: Mar 27, 2024

Russian Doll Envelopes

Author Husen Kagdi
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction 

Mike Mirzayanov and Gennady Korotkevich are two Russian programmers. They are going to organize a coding contest at Codeforces this Friday. So they are designing interesting problems for it. Since Dynamic Programming is an essential part of interviews, they are deciding to add a problem related to it. Dynamic Programming takes time to learn but once you get your hands dirty, it will be a cakewalk. They decided to add a problem namely, Russian Doll Envelopes. It is a 2D version of the famous longest increasing subsequence (LIS) problem. LIS states that given an array we need to find the maximum length subsequence of the array which is increasing, i.e., the adjacent elements of the subsequence are in an ordered fashion. Russian Doll Envelopes is a similar problem. So let us look at the problem statement now.

Also Read, Byte Array to String

Problem Statement

Given an array of envelopes where each envelope can be represented as its width and height, find out the maximum number of envelopes that we can Russian Doll (put inside each other).
An envelope can be put inside another envelope only if its width and height are strictly less than the other envelope’s width and height. We cannot rotate the envelopes.

Example

Envelopes = [[5, 12], [6, 10], [2, 7], [1, 4]]

Here we can put the fourth envelope into the third envelope. Because 1 <= 2 and 4 <= 7. Next, we can put the third envelope into either the first or second envelope. Because 2 <= 5 and 7 <= 12 or 2<=6 and 7 <= 10. Thus the maximum number of envelopes that can be put inside each other is equal to 3. Thus the answer is 3.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Recursive Approach

First, we apply the brute force approach. In this approach, we iterate over all possible sequences and try to find the longest increasing subsequence from them. We are able to achieve this using recursion. First, we try to find a recursive solution and later try to optimize it using dynamic programming if there are overlapping subproblems.

Initially, we set the values of two integer variables, MAX_HEIGHT' as INF and 'MAX_WIDTH’ as INF, where INF stands for infinity. The maximum height and width of the envelope that can be placed inside will be maintained by these variables. Then we experiment with all potential techniques of making Russian doll envelopes in order to determine the maximum number of envelopes that can be made Russian Doll. This can be accomplished by performing the steps below in each recursive call:

  1. Set the value of the integer variable 'MAX_ENVELOPE’ to 0.
  2. In each recursive call, iterate over all 'N' envelopes, and if the width of the envelope is strictly less than 'MAX_WIDTH' and the height of the envelope is strictly less than ‘MAX_HEIGHT' then try to place this envelope inside by making a recursive call with 'MAX_WIDTH' and 'MAX_HEIGHT' as the current envelope's width and height, respectively. Update the value of MAX_ENVELOPE' to the maximum of its current value plus 1 and the value returned in the recursive call.
  3. 'MAX_ENVELOPE' should be returned.

Return the recursive function's result, which is the maximum number of envelopes that the can Russian Doll.

Program

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

int helper(vector<int> &height, vector<int> &width, int n, int &maxHeight, int &maxWidth)
{
    int maxEnvelopes = 0;

    // Recursively try to find all the ways to russian doll envelope inside it.
    for (int i = 0; i < n; i++)
    {

        // Checking if the 'i'th envelopes fits.
        if (height[i] < maxHeight && width[i] < maxWidth)
        {
            maxEnvelopes = max(maxEnvelopes, 1 + helper(height, width, n, height[i], width[i]));
        }
    }

    return maxEnvelopes;
}

int russianDolls(vector<int> &height, vector<int> &width, int n)
{
    // Maximum Height and Width of envelopes that can be placed.
    int maxHeight = INT_MAX, maxWidth = INT_MAX;
    // Recursively find the maximum number of envelopes that can Russian Doll.
    return helper(height, width, n, maxHeight, maxWidth);
}

int maxEnvelopes(vector<vector<int>> &a)
{
    int l = a.size();
    vector<int> height(l);
    vector<int> width(l);

    // Create the width and height array from array a.
    for (int i = 0; i < l; i++)
    {
        height[i] = a[i][1];
        width[i] = a[i][0];
    }

    return russianDolls(height, width, l);
}

int main()
{
    // Taking user input.
    int n;
    cin >> n;
    vector<vector<int>> envelopes;
    vector<int> temp(2);

    for (int i = 0; i < n; i++)
    {
        int width, height;
        cin >> width >> height;

        temp[0] = width;
        temp[1] = height;

        envelopes.push_back(temp);
    }

    // Calling 'maxEnvelopes()' function to find the number of envelopes that can russian doll.
    cout << maxEnvelopes(envelopes);
    return 0;
}

Input

4
5 12
6 10
2 7
1 4

Output

3

Time Complexity

O(N!), where ‘N’ is the size of the array.
The above brute force approach has an O(N!) time complexity. In the worst-case scenario, the first call to the ‘helper’ function can result in ‘N’ further calls, each of which can result in ‘N - 1’ more recursive calls, and so on.

Space Complexity

O(N), where ‘N’ is the size of the array.
Because of the function call stack, the space complexity is O(N). It can reach a maximum size of ‘N’. Each function record is assumed to take up a fixed amount of space. As a result, the space complexity is O(N * 1), or O (N).

Dynamic Programming Approach

The approach is similar to the longest increasing subsequence problem. Here we are working on two items instead of one. Now, the longest increasing subsequence problem states that given an array, we need to find the longest sequence of elements which is increasing among all the possible increasing subsequences. Here we are just working on a 2D array instead of the 1D array. Here, we 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.

 To solve the problem follow these steps:

  1. Make an integer matrix ‘ENVELOPES' of dimension(N, 2).
  2. Run a loop with i ranging from 0 to N - 1 and set ENVELOPES[i][0] = HEIGHT[i] and ENVELOPES[i][1] = WIDTH[i] for each i.
  3. Sort the 'BOXES' in the matrix in a non-descending order of height. If two boxes have the same height, arrange them in non-increasing width order.
  4. The length of the longest increasing subsequence of widths, i.e., the second column of matrix 'ENVELOPES,' will now be the maximum number of boxes we can Russian Doll.
  5. Make an integer 'ARR’ with the size 'N' and duplicate the second column of matrix 'ENVELOPES' into array ‘TEMP’ while retaining the order.
  6. Return the length of the longest increasing subsequence of array ‘ARR’.

Program

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

int maxEnvelopes(vector<vector<int>> &arr)
{
    int n = arr.size();
    vector<int> dp;
    /*
        Sorting the array:
        If the first key is equal, then the second key must be in increasing order.
    */
    sort(arr.begin(), arr.end(), [&](vector<int> &x, vector<int> &y)
        { return x[0] < y[0] || (x[0] == y[0] && x[1] > y[1]); });

    // Start by pushing first height.
    dp.push_back(arr[0][1]);

    for (int i = 1; i < n; ++i)
    {
        int currHeight = arr[i][1];

        // Finding the element just greater than or equal to 'CURR_HEIGHT'.
        auto it = lower_bound(dp.begin(), dp.end(), currHeight);

        // If iterator points to end of array then we found an element contributing to the length of increasing subsequence.
        if (it == dp.end())
        {
            dp.push_back(currHeight);
        }

        else if (*it > currHeight)
        {
            dp[it - dp.begin()] = currHeight;
        }
    }
    return dp.size();
}

int main()
{
    // Taking user input.
    int n;
    cin >> n;
    vector<vector<int>> envelopes;
    vector<int> temp(2);

    for (int i = 0; i < n; i++)
    {
        int width, height;
        cin >> width >> height;

        temp[0] = width;
        temp[1] = height;

        envelopes.push_back(temp);
    }

    // Calling 'maxEnvelopes()' function to find the number of envelopes that can russian doll.
    cout << maxEnvelopes(envelopes);
    return 0;
}

Input

4
5 12
6 10
2 7
1 4

Output

3

Time Complexity

O(N*log(N)), where ‘N’ is the size of the array.
The time complexity of the above algorithm is O(N * log(N)). Initially, we are sorting the envelopes array which takes O(N*log(N)). Then in the loop, we are calling the lower_bound() function for ‘N’ times. Each time it takes O(log(N)) time. So overall it takes O(Nlog(N)) time.

Space Complexity

O(N), where N is the size of the array.
The space complexity is O(N) as we are using a DP array of size N. DP array stores the results of smaller problems.

Check out Longest Common Substring

Key Takeaways

In this blog, we learned how to solve an interesting problem, namely Russian Doll Envelopes. We solved the problem with two different approaches. First, we applied brute force which takes O(N!) time. Next, we took the aid of dynamic programming which reduced our time complexity to O(N*log(N)) Stay tuned for learning more concepts like this.

Thanks and Happy Coding!

Previous article
Count of sequence of length K in the range [1, N] where every element is a multiple of its previous one
Next article
Numbers with Repeated Digits
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass