Russian Doll Envelopes

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!