Leetcode: 354. Russian Doll Envelopes

Mistake: Incorrect evaluation of solution's viability. The constant factor of Segment Tree was too high to get an AC.
Mistake: Did not try hard to solve alternative problem. I found many useful properties but couldn't put all them together (e.g. sort envelopes first by increase \(h\) and then decreasing \(w\)).
Can we pre-process the input in a way to make easy to solve the problem? Sort the envelopes by \(h\) values. Now the problem becomes finding Longest Increasing Subsequence on values of \(w\). To avoid creating number with same \(h\), we make sure that \(h\) values are increase and \(w\) values with same \(h\) value is in decrease order. Time complexity is \(O(n \log n)\) and space is \(O(k)\) where \(k\) is the size of the longest subsequence.

from typing import List
from bisect import bisect_left


class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        N = len(envelopes)
        envelopes.sort(key=lambda e: (e[1], -e[0]))
        seq = []
        for n, _ in envelopes:
            k = bisect_left(seq, n)
            if k == len(seq):
                seq.append(n)
            else:
                seq[k] = n
        return len(seq)


assert Solution().maxEnvelopes([[5, 4], [6, 4], [6, 7], [2, 3]]) == 3
assert Solution().maxEnvelopes([[1, 1], [1, 1], [1, 1]]) == 1

Can we formulate the problem using a segment tree? Sort the envelopes by \(h\) and from the last to the first. Add them to a Segment Tree or FenwickTree which supports getting the max value of an interval. Time complexity is \(O(n \log m)\) where \(m\) is the max size of the interval, and space is \(O(m)\).

from typing import List


class FenwickTreeMax:
    def __init__(self, n):
        self.n = n
        self.bit = [float("-inf")] * n

    def getmax(self, r):
        ret = float("-inf")
        while r >= 0:
            ret = max(ret, self.bit[r])
            r = (r & (r + 1)) - 1
        return ret

    def update(self, idx, val):
        while idx < self.n:
            self.bit[idx] = max(self.bit[idx], val)
            idx = idx | (idx + 1)


class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        M = 123_456
        best = FenwickTreeMax(M)

        envelopes.sort(key=lambda e: (e[1], -e[0]))
        ans = 0
        for i in range(len(envelopes) - 1, -1, -1):
            n = envelopes[i][0]
            c = max(1, 1 + best.getmax(M - (n + 1)))
            best.update(M - n, c)
            ans = max(ans, c)
        return ans


assert Solution().maxEnvelopes([[5, 4], [6, 4], [6, 7], [2, 3]]) == 3
assert Solution().maxEnvelopes([[1, 1], [1, 1], [1, 1]]) == 1