classSolution {
publicintmaxEnvelopes(int[][] envelopes) {
int n = envelopes.length;
if (n == 0) return 0;
Arrays.sort(envelopes, (a, b) -> a[0]- b[0]);
int[] dp =newint[n + 1];
Arrays.fill(dp, 1);
int ans = 1;
for (int i = 1; i<n; ++i) {
for (int j = 0; j<i; ++j) {
if (envelopes[i][0]> envelopes[j][0]&& envelopes[i][1]> envelopes[j][1]) {
dp[i]= Math.max(dp[i], 1 + dp[j]);
}
ans = Math.max(ans, dp[i]);
}
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution {
funmaxEnvelopes(envelopes: Array<IntArray>): Int {
val n = envelopes.size
if (n ==0) return0 envelopes.sortWith(compareBy({ it[0] }, { it[1] }))
val dp = IntArray(n) { 1 }
var ans = 1for (i in1 until n) {
for (j in0 until i) {
if (envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1]) {
dp[i] = maxOf(dp[i], dp[j] + 1)
}
ans = maxOf(ans, dp[i])
}
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from typing import List
classSolution:
defmaxEnvelopes(self, envelopes: List[List[int]]) -> int:
n = len(envelopes)
if n ==0:
return0 envelopes.sort()
dp = [1] * n
ans =1for i in range(1, 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)
ans = max(ans, dp[i])
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
impl Solution {
pubfnmax_envelopes(mut envelopes: Vec<Vec<i32>>) -> i32 {
let n = envelopes.len();
if n ==0 { return0; }
envelopes.sort();
letmut dp = vec![1; n];
letmut ans =1;
for i in1..n {
for j in0..i {
if envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1] {
dp[i] = dp[i].max(dp[j] +1);
}
ans = ans.max(dp[i]);
}
}
ans
}
}
If width are equal then sort height in decreasing order. Because when width are same, most remaining envelopes can fit in the biggest envelope of same width, i.e. biggest height.
For eg. [3, 4] cannot contains [3, 3], so we need to put [3, 4] before [3, 3] when sorting otherwise it will be counted as an increasing number if the order is [3, 3], [3, 4]
Sorting the width reduces the problem by one dimension. If width is strictly increasing, the problem is equivalent to finding LIS in only the height dimension.
Now lets apply the LIS algo on height. We build a DP array.
In DP array, we fill in height from left to right. Initially all heights are 0.
For first height, we check if binary search returns something. That is the left place where the height can be inserted. If that matches current index, we increment ans.
In java, instead of writing our own method, we can also use Arrays.binarySearch(int[] array, int fromIndex, int toIndex, int target) method.
import"sort"typeSolutionstruct{}
func (Solution) MaxEnvelopes(envelopes [][]int) int {
sort.Slice(envelopes, func(i, jint) bool {
ifenvelopes[i][0] ==envelopes[j][0] {
returnenvelopes[i][1] > envelopes[j][1]
}
returnenvelopes[i][0] < envelopes[j][0]
})
dp:= []int{}
for_, env:=rangeenvelopes {
h:=env[1]
l, r:=0, len(dp)
forl < r {
m:=l+ (r-l)/2ifdp[m] < h {
l = m+1 } else {
r = m }
}
ifl== len(dp) {
dp = append(dp, h)
} else {
dp[l] = h }
}
return len(dp)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution {
publicintmaxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, (a,b) -> a[0]== b[0]? b[1]- a[1] : a[0]- b[0]);
int[] dp =newint[envelopes.length];
int ans = 0;
for (int[] envelope : envelopes) {
int height = envelope[1];
int left = binarySearch(dp, 0, ans, height);
if(left < 0) {
left =-(left + 1);}
if (left == ans) ans++;
dp[left]= height;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution {
funmaxEnvelopes(envelopes: Array<IntArray>): Int {
envelopes.sortWith(compareBy({ it[0] }, { -it[1] }))
val dp = mutableListOf<Int>()
for (env in envelopes) {
val h = env[1]
val idx = dp.binarySearch(h)
val insertIdx = if (idx < 0) -idx - 1else idx
if (insertIdx == dp.size) dp.add(h)
else dp[insertIdx] = h
}
return dp.size
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
from bisect import bisect_left
from typing import List
classSolution:
defmaxEnvelopes(self, envelopes: List[List[int]]) -> int:
envelopes.sort(key=lambda x: (x[0], -x[1]))
dp = []
for _, h in envelopes:
idx = bisect_left(dp, h)
if idx == len(dp):
dp.append(h)
else:
dp[idx] = h
return len(dp)
sorted by width envelopes =[[1,1],[2,3],[4,6],[4,5],[6,7]]Searching for height of 1Result of search:-1Inserting height at index:0dp: 10000l is now 1Searching for height of 3Result of search:-2Inserting height at index:1dp: 13000l is now 2Searching for height of 6Result of search:-3Inserting height at index:2dp: 13600l is now 3Searching for height of 5Result of search:-3Inserting height at index:2dp: 13500l is now 3Searching for height of 7Result of search:-4Inserting height at index:3dp: 13570l is now 4Max number of envelopes:4