1. Dynamic Programming (Top-Down)

Intuition

This problem is essentially finding the longest chain of envelopes where each envelope strictly contains the previous one. If we sort envelopes by width, we only need to find the longest increasing subsequence (LIS) of heights. The trick is to sort by width ascending, but when widths are equal, sort by height descending. This prevents envelopes with the same width from being part of the same chain, since we need strictly greater dimensions for both.

Algorithm

1. Sort envelopes by width ascending. For equal widths, sort by height descending.
2. Extract the heights into an array.
3. Use memoized recursion to compute LIS on the heights:
   • For each index i, recursively find the longest subsequence starting from i.
   • Check all indices j > i where heights[j] > heights[i], taking the maximum.
4. Return the maximum LIS value across all starting positions.

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        n = len(envelopes)
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        def lis(nums):
            n = len(nums)
            memo = [-1] * n

            def dfs(i):
                if memo[i] != -1:
                    return memo[i]

                LIS = 1
                for j in range(i + 1, n):
                    if nums[i] < nums[j]:
                        LIS = max(LIS, 1 + dfs(j))

                memo[i] = LIS
                return LIS

            return max(dfs(i) for i in range(n))

        return lis([e[1] for e in envelopes])

Time & Space Complexity

• Time complexity: $O(n ^ 2)$
• Space complexity: $O(n)$

---

2. Dynamic Programming (Bottom-Up)

Intuition

Instead of using recursion, we can build the solution iteratively from right to left. For each position, we compute the length of the longest increasing subsequence starting from that position by looking at all valid successors. This bottom-up approach avoids the overhead of recursion and explicitly fills a DP table.

Algorithm

1. Sort envelopes by width ascending, height descending for equal widths.
2. Extract heights into an array.
3. Create a DP array where LIS[i] represents the longest increasing subsequence starting at index i.
4. Iterate from right to left:
   • For each index i, check all j > i where heights[j] > heights[i].
   • Update LIS[i] = max(LIS[i], 1 + LIS[j]).
5. Return the maximum value in the LIS array.

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        n = len(envelopes)
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        def lis(nums):
            LIS = [1] * n

            for i in range(n - 1, -1, -1):
                for j in range(i + 1, n):
                    if nums[i] < nums[j]:
                        LIS[i] = max(LIS[i], 1 + LIS[j])
            return max(LIS)

        return lis([e[1] for e in envelopes])

Time & Space Complexity

• Time complexity: $O(n ^ 2)$
• Space complexity: $O(n)$

---

3. Dynamic Programming + Binary Search

Intuition

The standard LIS problem can be solved in O(n log n) using binary search. We maintain a list where each position stores the smallest ending value of all increasing subsequences of that length. For each new element, we either extend the longest subsequence or replace an existing ending value to allow for potentially longer subsequences later. Binary search finds the correct position efficiently.

Algorithm

1. Sort envelopes by width ascending, height descending for equal widths.
2. Extract heights into an array.
3. Initialize an empty list dp that will store the smallest tail values for subsequences of each length.
4. For each height:
   • If it's larger than the last element in dp, append it (extends the longest subsequence).
   • Otherwise, use binary search to find the first element in dp that is greater than or equal to the current height, and replace it.
5. The length of dp is the answer.

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        def lis(nums):
            dp = []
            dp.append(nums[0])

            LIS = 1
            for i in range(1, len(nums)):
                if dp[-1] < nums[i]:
                    dp.append(nums[i])
                    LIS += 1
                    continue

                idx = bisect_left(dp, nums[i])
                dp[idx] = nums[i]

            return LIS

        return lis([e[1] for e in envelopes])

Time & Space Complexity

• Time complexity: $O(n \log n)$
• Space complexity: $O(n)$

---

4. Segment Tree

Intuition

A segment tree can efficiently answer range maximum queries, which helps compute LIS. For each height, we query the maximum LIS length among all smaller heights, add one, and update the tree with this new value. Coordinate compression reduces the height values to a manageable range. This approach achieves the same O(n log n) complexity as binary search but offers a different perspective using range queries.

Algorithm

1. Sort envelopes by width ascending, height descending for equal widths.
2. Extract and compress heights to consecutive integers starting from 0.
3. Build a segment tree that supports range maximum queries and point updates.
4. For each compressed height h:
   • Query the maximum LIS value in the range [0, h - 1].
   • The current LIS ending at h is query result + 1.
   • Update the segment tree at position h with this value.
5. Return the maximum LIS value found.

class SegmentTree:
    def __init__(self, N):
        self.n = N
        while (self.n & (self.n - 1)) != 0:
            self.n += 1
        self.tree = [0] * (2 * self.n)

    def update(self, i, val):
        self.tree[self.n + i] = val
        j = (self.n + i) >> 1
        while j >= 1:
            self.tree[j] = max(self.tree[j << 1], self.tree[j << 1 | 1])
            j >>= 1

    def query(self, l, r):
        if l > r:
            return 0
        res = float('-inf')
        l += self.n
        r += self.n + 1
        while l < r:
            if l & 1:
                res = max(res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res = max(res, self.tree[r])
            l >>= 1
            r >>= 1
        return res

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        n = len(envelopes)
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        def lis(nums):
            def compress(arr):
                sortedArr = sorted(set(arr))
                order = []
                for num in arr:
                    order.append(bisect_left(sortedArr, num))
                return order

            nums = compress(nums)
            n = len(nums)
            segTree = SegmentTree(n)

            LIS = 0
            for num in nums:
                curLIS = segTree.query(0, num - 1) + 1
                segTree.update(num, curLIS)
                LIS = max(LIS, curLIS)
            return LIS

        return lis([e[1] for e in envelopes])

Time & Space Complexity

• Time complexity: $O(n \log n)$
• Space complexity: $O(n)$

Common Pitfalls

Sorting Heights in Wrong Order for Equal Widths

The most critical mistake is sorting by height ascending when widths are equal. This allows multiple envelopes with the same width to be included in the LIS, violating the strict containment requirement. When widths are equal, sort heights in descending order to ensure only one envelope per width can be selected.

Using Non-Strict Inequality for Containment

Some solutions check width1 <= width2 and height1 <= height2 instead of strict inequality. Envelopes must strictly contain each other, meaning both dimensions must be strictly greater. Using <= incorrectly allows envelopes of equal size to be nested.

Applying Standard LIS Without Dimension Reduction

Attempting to run LIS on both dimensions simultaneously leads to an incorrect or overly complex solution. The key insight is that after sorting by width, the problem reduces to finding LIS on heights alone. Failing to recognize this reduction results in unnecessary complexity or wrong answers.

Off-by-One Errors in Binary Search

When implementing the O(n log n) LIS solution, using the wrong binary search variant causes errors. You need to find the first element greater than or equal to the current height (lower bound), not strictly greater. Using upper bound or incorrect comparisons leads to wrong LIS lengths.