354. Russian Doll Envelopes

  • 31.9%

https://leetcode.com/problems/russian-doll-envelopes/

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

1
2
3
4
Example:
Given envelopes = [[5,4],[6,4],[6,7],[2,3]],
the maximum number of envelopes you can Russian doll
is 3 ([2,3] => [5,4] => [6,7]).

java


https://discuss.leetcode.com/topic/47469/java-nlogn-solution-with-explanation

Java NLogN Solution with Explanation

  1. Sort the array. Ascend on width and descend on height if width are same.
  2. Find the longest increasing subsequence based on height.
  • Since the width is increasing, we only need to consider height.
  • [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]
  • 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    public int maxEnvelopes(int[][] envelopes) {
    if(envelopes == null || envelopes.length == 0
    || envelopes[0] == null || envelopes[0].length != 2)
    return 0;
    Arrays.sort(envelopes, new Comparator<int[]>(){
    public int compare(int[] arr1, int[] arr2){
    if(arr1[0] == arr2[0])
    return arr2[1] - arr1[1];
    else
    return arr1[0] - arr2[0];
    }
    });
    int dp[] = new int[envelopes.length];
    int len = 0;
    for(int[] envelope : envelopes){
    int index = Arrays.binarySearch(dp, 0, len, envelope[1]);
    if(index < 0)
    index = -(index + 1);
    dp[index] = envelope[1];
    if(index == len)
    len++;
    }
    return len;
    }

https://discuss.leetcode.com/topic/47469/java-nlogn-solution-with-explanation/2

clever solution, here is my C++ version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
static bool cmp_first(const pair<int, int>& i, const pair<int, int>& j) {
if (i.first == j.first)
return i.second > j.second;
return i.first < j.first;
}
int maxEnvelopes(vector<pair<int, int>>& envelopes) {
vector<int> candidates;
sort(envelopes.begin(), envelopes.end(), cmp_first);
vector<int> dp;
for (int i = 0; i < envelopes.size(); ++i) {
auto itr = lower_bound(dp.begin(), dp.end(), envelopes[i].second);
if (itr == dp.end()) {
dp.push_back(envelopes[i].second);
} else {
*itr = envelopes[i].second;
}
}
return dp.size();
}
};

What a concise and comprehensive explanation!

Here is my Python code following your thought:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from bisect import bisect_left

class Solution(object):
def maxEnvelopes(self, envelopes):
if not envelopes:
return 0
envelopes.sort(key=lambda x: (x[0], -x[1]))
max_idx = 0
heights = [envelopes[0][1]] + [0] * (len(envelopes) - 1)
for e in envelopes:
idx = bisect_left(heights, e[1], hi=max_idx + 1)
heights[idx] = e[1]
max_idx = max(max_idx, idx)
return max_idx + 1

https://discuss.leetcode.com/topic/47404/simple-dp-solution

Simple DP solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
}

https://discuss.leetcode.com/topic/47594/short-and-simple-java-solution-15-lines

Short and simple Java solution (15 lines)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxEnvelopes(int[][] envelopes) {
Arrays.sort(envelopes, (a, b) -> a[0] - b[0]);
int max = 0;
int dp [] = new int [envelopes.length];
for(int i = 0; i < envelopes.length; i++){
dp[i] = 1;
for(int j = 0; j < i; j++){
if(envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1])
dp[i] = Math.max(dp[i], dp[j] + 1);
}
max = Math.max(dp[i], max);
}
return max;
}

cpp


https://discuss.leetcode.com/topic/47406/c-dp-version-time-o-n-2-space-o-n

C++ DP version, Time O(N^2) Space O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool cmp (pair<int, int> i, pair<int, int> j) {
if (i.first == j.first)
return i.second < j.second;
return i.first < j.first;
}

class Solution {
public:
int maxEnvelopes(vector<pair<int, int>>& envelopes) {
int N = envelopes.size();
vector<int> dp(N, 1);
int mx = (N == 0) ? 0 : 1;
sort(envelopes.begin(), envelopes.end(), cmp);
for (int i = 0; i < N; i++) {
for (int j = i - 1; j >= 0; j--) {
if (envelopes[i].first > envelopes[j].first && envelopes[i].second > envelopes[j].second) {
dp[i] = max(dp[i], dp[j] + 1);
mx = max(dp[i], mx);
}
}
}
return mx;
}
};

https://discuss.leetcode.com/topic/47684/c-9-line-short-and-clean-o-nlogn-solution-plus-classic-o-n-2-dp-solution

C++ 9-line Short and Clean O(nlogn) solution (plus classic O(n^2) dp solution).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
///O(nlogn)

struct Solution {
int maxEnvelopes(vector<pair<int, int>>& es) {
sort(es.begin(), es.end(), [](pair<int, int> a, pair<int, int> b){
return a.first < b.first || (a.first == b.first && a.second > b.second);});
vector<int> dp;
for (auto e : es)
{
auto iter = lower_bound(dp.begin(), dp.end(), e.second);
if (iter == dp.end())
dp.push_back(e.second);
else if (e.second < *iter)
*iter = e.second;
}
return dp.size();
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
///DP

struct Solution {
int maxEnvelopes(vector<pair<int, int>>& envelopes) {
if (envelopes.empty()) return 0;
sort(envelopes.begin(), envelopes.end());
vector<int> dp(envelopes.size(), 1);
for (int i = 0; i < envelopes.size(); ++i)
for (int j = 0; j < i; ++j)
if (envelopes[j].first < envelopes[i].first && envelopes[j].second < envelopes[i].second)
dp[i] = max(dp[i] , dp[j] + 1);
return *max_element(dp.begin(), dp.end());
}
};

python


https://discuss.leetcode.com/topic/47443/clean-and-short-nlogn-solution

Clean and short nlogn solution

See more explanation in Longest Increasing Subsequence Size (N log N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def maxEnvelopes(self, envelopes):
def bin_search(A, key):
l, r = 0, len(A)
while l < r:
mid = (l+r)/2
if A[mid][1] < key[1]:
l = mid + 1
else:
r = mid
return l
envelopes.sort(
cmp = lambda x,y: x[0]-y[0] if x[0] != y[0] else y[1]-x[1])
n = len(envelopes)
tails = []
for i in range(n):
e = envelopes[i]
p = bin_search(tails, e)
if p == len(tails):
tails.append(e)
else:
tails[p] = e
return len(tails)

https://discuss.leetcode.com/topic/48160/python-o-nlogn-o-n-solution-beats-97-with-explanation

Python O(nlogn) O(n) solution, beats 97%, with explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution(object):
def maxEnvelopes(self, envs):
def liss(envs):
def lmip(envs, tails, k):
b, e = 0, len(tails) - 1
while b <= e:
m = (b + e) >> 1
if envs[tails[m]][1] >= k[1]:
e = m - 1
else:
b = m + 1
return b

tails = []
for i, env in enumerate(envs):
idx = lmip(envs, tails, env)
if idx >= len(tails):
tails.append(i)
else:
tails[idx] = i
return len(tails)


def f(x, y):
return -1 if (x[0] < y[0] or x[0] == y[0] and x[1] > y[1]) else 1

envs.sort(cmp=f)
return liss(envs)

# Runtime: 100ms

The idea is to order the envelopes and then calculate the longest increasing subsequence (LISS). We first sort the envelopes by width, and we also make sure that when the width is the same, the envelope with greater height comes first. Why? This makes sure that when we calculate the LISS, we don’t have a case such as [3, 4] [3, 5] (we could increase the LISS but this would be wrong as the width is the same. It can’t happen when [3, 5] comes first in the ordering).

We could calculate the LISS using the standard DP algorithm (quadratic runtime), but we can just use the tails array method with a twist: we store the index of the tail, and we do leftmost insertion point as usual to find the right index in nlogn time. Why not rightmost? Think about the case [1, 1], [1, 1], [1, 1].

谢谢你,可爱的朋友。