Russian Doll Envelopes — Sort + LIS Binary Search

Problem 340 · Russian Doll Envelopes

Difficulty: Hard · Pattern: Sort + LIS (patience sort)

Can only put envelope A inside B if both width and height are strictly smaller.

Intuition

Sort by width ASC, then by height DESC (for same width). Then find LIS on heights. DESC for same width prevents using two envelopes of the same width.

Solutions

# Python
import bisect
def maxEnvelopes(envelopes):
    envelopes.sort(key=lambda x: (x[0], -x[1]))
    tails = []
    for _, h in envelopes:
        pos = bisect.bisect_left(tails, h)
        if pos == len(tails): tails.append(h)
        else: tails[pos] = h
    return len(tails)

// Java
public int maxEnvelopes(int[][] env) {
    Arrays.sort(env, (a,b) -> a[0]!=b[0] ? a[0]-b[0] : b[1]-a[1]);
    List<Integer> tails = new ArrayList<>();
    for (int[] e : env) {
        int h=e[1], lo=0, hi=tails.size();
        while (lo<hi) { int mid=(lo+hi)/2; if(tails.get(mid)<h) lo=mid+1; else hi=mid; }
        if (lo==tails.size()) tails.add(h); else tails.set(lo,h);
    }
    return tails.size();
}

Complexity

Time: O(n log n)
Space: O(n)