Russian Doll Envelopes - Practice Coding Problems

Russian Doll Envelopes - Problem

You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Input & Output

Example 1 — Basic Nesting

$ Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]

› Output: 3

💡 Note: Maximum nesting: [2,3] → [5,4] → [6,7]. Each envelope fits inside the next: (2<5 and 3<4), then (5<6 and 4<7).

Example 2 — Single Envelope

$ Input: envelopes = [[1,1]]

› Output: 1

💡 Note: Only one envelope available, so maximum nesting is 1.

Example 3 — No Valid Nesting

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

› Output: 3

💡 Note: Best nesting: [1,1] → [2,3] → [4,5] or [1,1] → [2,3] → [6,7]. Can't nest [4,5] and [4,6] together since widths are equal.

Constraints

1 ≤ envelopes.length ≤ 10⁵
envelopes[i].length == 2
1 ≤ w_i, h_i ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Envelopes

Given envelopes with [width, height] dimensions

Valid Nesting

Envelope A fits in B if both width and height are strictly smaller

Maximum Chain

Find longest possible nesting sequence

Key Takeaway

🎯 Key Insight: Sort by one dimension, then solve longest increasing subsequence on the other

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Facebook 12

The key insight is to sort by width and transform into a Longest Increasing Subsequence problem on heights. The optimal approach uses binary search for O(n log n) complexity. Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Recursion	O(2^n)	O(n)	Try all possible combinations of envelopes to find maximum nesting
Sort + Binary Search LIS	O(n log n)	O(n)	Optimize LIS finding using binary search for O(n log n) solution
Sort + Dynamic Programming	O(n²)	O(n)	Sort envelopes by width, then find longest increasing subsequence by height

Brute Force with Recursion — Algorithm Steps

Try each envelope as starting point
For each envelope, recursively find all that can fit inside
Return maximum depth found

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Each Envelope

Start with each envelope as potential beginning

Recursive Search

For each choice, recursively find all valid nestings

Maximum Depth

Return the deepest nesting found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int canFit(int* env1, int* env2) {
    return env1[0] < env2[0] && env1[1] < env2[1];
}

int dfs(int envelopes[][2], int n, int index, int* currentEnvelope) {
    int maxCount = 0;
    for (int i = index; i < n; i++) {
        if (currentEnvelope == NULL || canFit(currentEnvelope, envelopes[i])) {
            int count = 1 + dfs(envelopes, n, i + 1, envelopes[i]);
            if (count > maxCount) {
                maxCount = count;
            }
        }
    }
    return maxCount;
}

int solution(int envelopes[][2], int n) {
    return dfs(envelopes, n, 0, NULL);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int envelopes[1000][2];
    int n = 0;
    
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            envelopes[n][0] = strtol(ptr, &ptr, 10);
            ptr++;
            envelopes[n][1] = strtol(ptr, &ptr, 10);
            n++;
        }
        ptr++;
    }
    
    printf("%d\n", solution(envelopes, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

For each envelope we try two choices: include or exclude, leading to exponential combinations

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion depth can go up to n envelopes

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~35 min Avg. Time

3.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler