354-russian-doll-envelopes

Try it on leetcode

Description

You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

 

Example 1:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Example 2:

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1

 

Constraints:

• 1 <= envelopes.length <= 105
• envelopes[i].length == 2
• 1 <= wi, hi <= 105

Solution(Python)

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        return self.binarysearch(envelopes)

    # Time Complexity: O(2^n)
    # Space Complexity: O(n)
    def bruteforce(self, envelopes: List[List[int]]) -> int:
        envelopes.sort()
        n = len(envelopes)

        def dfs(i):
            res = 1
            for j in range(i):
                if (
                    envelopes[i][0] > envelopes[j][0]
                    and envelopes[i][1] > envelopes[j][1]
                ):
                    res = max(res, 1 + dfs(j))
            return res

        maxlen = 0
        for i in range(n):
            maxlen = max(maxlen, dfs(i))
        return maxlen

    # Time Complexity: O(n^2)
    # Space Complexity: O(n)
    # H[j] = i<j{max(H(i))}+1
    def dynamicprogramming(self, envelopes: List[List[int]]) -> int:
        envelopes.sort()

        n = len(envelopes)
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if (
                    envelopes[i][0] > envelopes[j][0]
                    and envelopes[i][1] > envelopes[j][1]
                ):
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

    # Time Complexity: O(n^2)
    # Space Complexity: O(n)
    def sortingwithmemoize(self, envelopes: List[List[int]]) -> int:
        envelopes.sort()
        n = len(envelopes)
        dp = [-1] * n

        def dfs(i):
            if dp[i] != -1:
                return dp[i]
            res = 1
            for j in range(i):
                if (
                    envelopes[i][0] > envelopes[j][0]
                    and envelopes[i][1] > envelopes[j][1]
                ):
                    res = max(res, 1 + dfs(j))
            dp[i] = res
            return dp[i]

        maxlen = 0
        for i in range(n):
            maxlen = max(maxlen, dfs(i))
        return maxlen

    # Time Complexity: O(nlogn)
    # Space Complexity: O(n)
    def binarysearch(self, envelopes: List[List[int]]) -> int:
        envelopes.sort(key=lambda x: (x[0], -x[1]))
        dp = []
        for envelope in envelopes:
            pos = bisect.bisect_left(dp, envelope[1])
            if pos == len(dp):
                dp.append(envelope[1])
            else:
                dp[pos] = envelope[1]

        return len(dp)