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.
1import java.util.Arrays;
2public class Solution {
3 public int maxEnvelopes(int[][] envelopes) {
4 Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
5 int[] dp = new int[envelopes.length];
6 int len = 0;
7 for (int[] envelope : envelopes) {
8 int index = Arrays.binarySearch(dp, 0, len, envelope[1]);
9 if (index < 0) index = -(index + 1);
10 dp[index] = envelope[1];
11 if (index == len) len++;
12 }
13 return len;
14 }
15}This Java solution uses the same logic as the Python solution. It sorts the envelopes first, then uses a binary search to maintain a dynamic programming array for finding the sequence length.
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.