354: Space 98.16%, Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n1. We first sort the envelopes based on width in ascending order, and if 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. We first sort the envelopes based on width in ascending order, and if the widths are equal, we sort them based on height in descending order. This is because when we are trying to find the maximum number of envelopes we can Russian doll, we only care about the heights of the envelopes that have the same width as the current envelope, and we want to sort them in descending order so that we can maintain the largest possible doll set.\n\n2. We then initialize an array called doll_set to store the heights of the envelopes in the Russian doll set.\n\n3. We iterate through each envelope in the sorted envelopes list.\n\n4. For each envelope, we get its height and use binary search to find the index where we can insert the current height to maintain the sorted order of the doll set.\n\n5. If the index is beyond the length of the doll set, we add the height to the end of the doll set.\n\n6. Otherwise, we replace the height at that index with the current height, since it can fit inside the previous envelope.\n\n7. After iterating through all the envelopes, the length of the doll_set array is the maximum number of envelopes we can Russian doll, so we return it.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n  def maxEnvelopes(self, envelopes: List[List[int]]) -> int:\n    envelopes.sort(key=lambda x: (x[0], -x[1]))\n    # Same as 300. Longest Increasing Subsequence\n    ans = 0\n    dp = [0] * len(envelopes)\n\n    for _, h in envelopes:\n      l = 0\n      r = ans\n      while l < r:\n        m = (l + r) // 2\n        if dp[m] >= h:\n          r = m\n        else:\n          l = m + 1\n      dp[l] = h\n      if l == ans:\n        ans += 1\n\n    return ans\n\n```
['Array', 'Binary Search', 'Dynamic Programming', 'Python', 'Python3']