Hard

Russian Doll Envelopes

LAB

Given envelopes [width,height], return the maximum number that can be nested strictly by both dimensions.

EXAMPLES

Example 1

Input
{
  "envelopes": [
    [
      5,
      4
    ],
    [
      6,
      4
    ],
    [
      6,
      7
    ],
    [
      2,
      3
    ]
  ]
}

Output
3

FUNCTION SHAPE

envelopes: intMatrix→int

SOLUTION NOTE

Sort by width ascending. For same width, sort height descending (so we can't nest same-width envelopes). Then run LIS on heights.

Reveal reference solution +

pythonREFERENCE

def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
    # Sort by width ascending, height descending (for same width)
    envelopes.sort(key=lambda x: (x[0], -x[1]))

    # LIS on heights only
    heights = [h for w, h in envelopes]
    tails = []
    for h in heights:
        pos = bisect_left(tails, h)
        if pos == len(tails):
            tails.append(h)
        else:
            tails[pos] = h
    return len(tails)

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗