Russian Doll Envelopes

Leetcode Problem 354: Russian Doll Envelopes

Problem Summary

You are given a 2D array envelopes where envelopes[i] = [w_i, h_i] represents the width and height of an envelope. One envelope fits into another if and only if both its width and height are strictly smaller than the other envelope's width and height. Return the maximum number of envelopes you can put one inside the other. The array contains between 1 and 10^5 envelopes, and each dimension is in the range [1, 10^5].

Techniques

Array
Binary Search
Dynamic Programming
Sorting

Solution

function maxEnvelopes(envelopes: number[][]): number {
    envelopes.sort((a, b) => {
        if (a[0] === b[0]) {
            return b[1] - a[1]
        }

        return a[0] - b[0]
    })
    const heights = envelopes.map(e => e[1])
    const tails: number[] = []

    for (const h of heights) {
        let left = 0
        let right = tails.length

        while (left < right) {
            const mid = Math.floor((left + right) / 2)
            if (tails[mid] < h) {
                left = mid + 1
            } else {
                right = mid
            }
        }

        if (left === tails.length) {
            tails.push(h)
        } else {
            tails[left] = h
        }
    }

    return tails.length
}