LC-0354 Hard LeetCode

354. Russian Doll Envelopes

Array Binary Search Dynamic Programming Sorting

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 37% Topics: Array, Binary Search, Dynamic Programming, Sorting

Reading material

Arrays & Hashing 12 min Binary Search 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(nlogn + nlogk) = O(nlogn), k is the length of the result.
# Space: O(1)

class Solution(object):
    def maxEnvelopes(self, envelopes):
        """
        :type envelopes: List[List[int]]
        :rtype: int
        """
        def insert(target):
            left, right = 0, len(result) - 1
            while left <= right:
                mid = left + (right - left) / 2
                if result[mid] >= target:
                    right = mid - 1
                else:
                    left = mid + 1
            if left == len(result):
                result.append(target)
            else:
                result[left] = target

        result = []

        envelopes.sort(lambda x, y: y[1] - x[1] if x[0] == y[0] else \
                                    x[0] - y[0])
        for envelope in envelopes:
            insert(envelope[1])

        return len(result)

Solution from kamyu104/LeetCode-Solutions · MIT