Russian Doll Envelopes

hard dp LIS binary search

Problem

You are given envelopes [w, h]. Envelope A can nest inside B iff A.w < B.w and A.h < B.h. Return the maximum number of envelopes you can nest.

Inputenvelopes = [[5,4],[6,4],[6,7],[2,3]]

Output3

Sort by width ASC, height DESC (to forbid equal-width nesting), then LIS on heights.

envelopes (JSON list of [w,h])

from bisect import bisect_left

def max_envelopes(envs):
    envs.sort(key=lambda e: (e[0], -e[1]))
    tails = []
    for _, h in envs:
        i = bisect_left(tails, h)
        if i == len(tails):
            tails.append(h)
        else:
            tails[i] = h
    return len(tails)

function maxEnvelopes(envs) {
  envs.sort((a, b) => a[0] - b[0] || b[1] - a[1]);
  const tails = [];
  for (const [, h] of envs) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const m = (lo + hi) >> 1;
      if (tails[m] < h) lo = m + 1; else hi = m;
    }
    if (lo === tails.length) tails.push(h);
    else tails[lo] = h;
  }
  return tails.length;
}

class Solution {
    public int maxEnvelopes(int[][] envs) {
        Arrays.sort(envs, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        int[] tails = new int[envs.length];
        int sz = 0;
        for (int[] e : envs) {
            int lo = 0, hi = sz;
            while (lo < hi) { int m = (lo + hi) >>> 1; if (tails[m] < e[1]) lo = m + 1; else hi = m; }
            tails[lo] = e[1];
            if (lo == sz) sz++;
        }
        return sz;
    }
}

int maxEnvelopes(vector<vector<int>>& envs) {
    sort(envs.begin(), envs.end(), [](auto& a, auto& b) {
        return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1];
    });
    vector<int> tails;
    for (auto& e : envs) {
        auto it = lower_bound(tails.begin(), tails.end(), e[1]);
        if (it == tails.end()) tails.push_back(e[1]); else *it = e[1];
    }
    return tails.size();
}

Explanation

An envelope fits inside another only if both width and height are strictly larger. Handling two dimensions at once is hard, so the trick is to sort first and reduce the problem to a single dimension.

We sort by width ascending, and for ties in width we sort by height descending. That descending tiebreak is the clever bit: it guarantees two envelopes with the same width can never both be picked, because their heights now go the wrong way to form an increasing run.

After sorting, the answer is just the Longest Increasing Subsequence (LIS) of the heights — the longest chain where each height is strictly bigger than the last. Since width is already non-decreasing, an increasing height chain is a valid nesting.

We compute LIS fast with a tails array, where tails[i] is the smallest possible ending height of an increasing chain of length i+1. For each height we binary-search (bisect_left) for its slot: if it extends the longest chain we append, otherwise we overwrite to keep that length's tail as small as possible.

Example: [[5,4],[6,4],[6,7],[2,3]] sorts to widths 2,5,6,6 with heights 3,4,7,4. The LIS of heights is 3, 4, 7 (length 3), and the equal-width (6,4) is correctly excluded.

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