Sponsored
Sponsored
In this approach, we first sort the envelopes by width and then by height in descending order (if widths are equal). This allows us to look for the longest increasing subsequence of the heights while ignoring the widths. We then use a dynamic programming array to keep track of the maximum sequence length found so far.
Time Complexity: O(n log n), where n is the number of envelopes, due to sorting and binary search operations.
Space Complexity: O(n) for the dp array.
1def maxEnvelopes(envelopes):
2 envelopes.sort(key=lambda x: (x[0], -x[1]))
3 dp = []
4 for _, h in envelopes:
5 i = bisect_left(dp, h)
6 if i == len(dp):
7 dp.append(h)
8 else:
9 dp[i] = h
10 return len(dp)This Python solution sorts the envelopes, then iterates through them to find the longest increasing subsequence of heights using binary search from the bisect module.
This approach involves sorting and using a binary search to optimize the search through the height for the longest increasing subsequence. This enhances efficiency over a simple dynamic programming solution due to reduced overhead from repeated searches.
Time Complexity: O(n log n) because of sorting and binary search operations.
Space Complexity: O(n) to store the dp list.
1var maxEnvelopes = function(envelopes) {
2This JavaScript solution sorts envelopes and uses a two-pointer technique with binary search to track the longest sequence. The dp array is adjusted similarly in other language examples.