# Simple DP solution

• ``````public int maxEnvelopes(int[][] envelopes) {
if (   envelopes           == null
|| envelopes.length    == 0
|| envelopes[0]        == null
|| envelopes[0].length == 0){
return 0;
}

Arrays.sort(envelopes, new Comparator<int[]>(){
@Override
public int compare(int[] e1, int[] e2){
return Integer.compare(e1[0], e2[0]);
}
});

int   n  = envelopes.length;
int[] dp = new int[n];

int ret = 0;
for (int i = 0; i < n; i++){
dp[i] = 1;

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]);
}
}

ret = Math.max(ret, dp[i]);
}
return ret;
}``````

• Amazing code! I have a question. In comparator I tried to

return e1[0] - e2[0];

It gave me out of memory error. Could you please explain what's the different of these two operation? I thought they are same.

• May be overflow.
Integer. MAX - Integer. MIN

• It did for me once as well. I re-ran and the issue went away without changing any code.

• what is the time complexity for this solution?

• The runtime is O(n^2). The outer loop goes through all indices and the inner loop goes all the way up to the outer loop. So worst case is n^2.

• @dasahcc
You should use something like this:
'''
Arrays.sort(a, new Comparator<int[]>() {
public int compare(int a1[], int a2[]) {
return a1[0] * a1[1] - a2[0] * a2[1];
}
});
'''

• @raj29

I would never do something like a1[0] * a1[1] - a2[0] * a2[1] in a Comparator, that is going to expose us to an unexpected result due to Integer overflow

• @bdwalker definitely O(n^2). this solution is actually quite intuitive....

• I got the same thing, perhaps a little more verbose but I find it readable. BTW, this is an easier version of the box-stacking problem:

``````public int maxEnvelopes(int[][] envelopes) {
if (envelopes == null) return 0;
if (envelopes.length <= 1) return envelopes.length;
int max = 1, n = envelopes.length;
Arrays.sort(envelopes, (x, y) -> Integer.compare(y[0]*y[1], x[0]*x[1])); // sort by area
int[] dp = new int[n];
for(int i = 0; i < n; i++) {
dp[i] = 1;
int[] inner = envelopes[i];
for(int j = 0; j < i; j++) {
int[] outer = envelopes[j];
if (outer[0] > inner[0] && outer[1] > inner[1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
max = Math.max(max, dp[i]);
}
return max;
}
``````

• I came up with the same solution in the first round. Considering it is O(n^2) time complexity while consuming O(n) space, it is not good enough to be a "hire" solution....

• A nitpit: in the comparator function, there is no need for `@Override`.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.