LeetCode //C - 354. Russian Doll Envelopes

354. Russian Doll Envelopes

You are given a 2D array of integers envelopes where envelopes[i] = [ w i , h i w_i, h_i wi,hi] 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:

Example 2:

Constraints:

1 < = e n v e l o p e s . l e n g t h < = 1 0 5 1 <= envelopes.length <= 10^5 1<=envelopes.length<=105
envelopes[i].length == 2
1 < = w i , h i < = 1 0 5 1 <= wi, hi <= 10^5 1<=wi,hi<=105

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 order
        return 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 envelopes
    qsort(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 array
        int left = 0, right = len;
        while (left < right) {
            int mid = (left + right) / 2;
            if (dp[mid] < height)
                left = mid + 1;
            else
                right = mid;
        }

        // Replace element or append new length
        if (right >= len) {
            dp[len++] = height;
        } else {
            dp[right] = height;
        }
    }

    free(dp); // Clean up the dynamic array
    return len;
}

Navigator_Z