354. Russian Doll Envelopes

https://leetcode.com/problems/russian-doll-envelopes/

Python

DP with Binary Search (Bisect)

(Offical solution)

from bisect import bisect_left


class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        # On the same width, since we can only choose 'one' envelop
        # Reverse sort on the height to get select the max height envelop if they're in the same width
        envelopes.sort(key=lambda wh: (wh[0], -wh[1]))

        dp = []
        for i, (width, height) in enumerate(envelopes):
            # Binary Search the posistion to pick from the sequence of envelops
            pos = bisect_left(dp, height)
            if pos == len(dp):
                dp.append(height)
            else:
                dp[pos] = height

        return len(dp)

Javascript

var maxEnvelopes = function(envelopes) {
    
    envelopes.sort(([aW, aH], [bW, bH]) => {
        if (aW === bW) return bH - aH;
        return aW - bW;
    })
    
    const dp = [];
    for (let i = 0; i < envelopes.length; i++) {
        const h = envelopes[i][1];
        let left = 0;
        let right = dp.length;
        
        while (left < right) {
            let mid = (left + right) >> 1;
            if (dp[mid] < h) left = mid + 1;
            else right = mid;
        }    
        dp[left] = h;
    }
    
    
    return dp.length;
};