354. Russian Doll Envelopes

You are given a 2D array of integers envelopes where envelopes[i] = [$w_i,h_i$] represents the width and the 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.
 

Example 1:

**Input:**envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Example 2:

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

Constraints:

• $1<=envelopes.length<=10^5$
• envelopes[i].length == 2
• $1<=wi,hi<=10^5$

From: LeetCode
Link: 354. Russian Doll Envelopes

---

Solution:

Ideas:

1. Sort the Envelopes:

• Sort the envelopes by width in ascending order. If two envelopes have the same width, sort them by height in descending order. This way, envelopes with the same width can’t be placed one inside the other, which simplifies the logic for the LIS step.

2. Find the Longest Increasing Subsequence:

• After sorting, the problem boils down to finding the longest increasing sequence based on the height. This can be efficiently performed using a dynamic programming approach or more optimally with a method that uses binary search.

3. Dynamic Programming with Binary Search:

• You can use a binary search technique to maintain a list of potential ending heights for LIS of different lengths, improving the time complexity from O(n^2) (pure dynamic programming) to O(n log n).

Code:

// Comparator function for qsort
int compare(const void *a, const void *b) {int *envelopeA = *(int **)a;int *envelopeB = *(int **)b;if (envelopeA[0] == envelopeB[0]) // If widths are the same, sort by height in descending orderreturn envelopeB[1] - envelopeA[1];return envelopeA[0] - envelopeB[0]; // Otherwise, sort by width in ascending order
}int maxEnvelopes(int** envelopes, int envelopesSize, int* envelopesColSize) {if (envelopesSize == 0) return 0;// Sort envelopesqsort(envelopes, envelopesSize, sizeof(int*), compare);// This will store the increasing heights (dynamic array for the potential LIS)int *dp = (int *)malloc(envelopesSize * sizeof(int));int len = 0;for (int i = 0; i < envelopesSize; i++) {int height = envelopes[i][1];// Binary search for the height in the dp arrayint left = 0, right = len;while (left < right) {int mid = (left + right) / 2;if (dp[mid] < height)left = mid + 1;elseright = mid;}// Replace element or append new lengthif (right >= len) {dp[len++] = height;} else {dp[right] = height;}}free(dp); // Clean up the dynamic arrayreturn len;
}