BinarySearch 0372 Boxes All the Way Down

Problem statement

https://binarysearch.com/problems/Boxes-All-the-Way-Down/

Solution

Equal to Leetcode 0354. Russian Doll Envelopes.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, matrix):
        nums = sorted(matrix, key = lambda x: [x[0], -x[1]])    
        dp = [10**10] * (len(nums) + 1)
        for elem in nums: dp[bisect_left(dp, elem[1])] = elem[1]  
        return dp.index(10**10)