# Share My 39ms C++ solution with binary search

• This problem can be reduced to find longest increasing subsequence with binary search.

Algorithm

1. Sort the `envelopes` according to the `first` number of each envelope. If the first numbers are the same for i-th and j-th envelops , ordered them by their second number with decreasing order.
Ex: [[2, 3], [2, 4]] --> [[2, 4], [2, 3]]

2. After sorting, the problem become find the longest subsequence from the second number of each envelope. So, we can apply LeetCode 300's solution as following:

Time Complexity

1. Best case: the second number of the sorted envelopes is in increasing order. O(n)
2. Average case: For each envelope, we have to find it position with binary search in `LIS` (O(log(n))). So, totally, O(nlog(n))

Solution for finding LIS

``````class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int N = nums.size();
if(N == 0) return 0;
vector<int> LIS;
LIS.push_back(nums[0]);

for(int i = 1; i < N; i++) {
if(nums[i] > LIS.back())
LIS.push_back(nums[i]);
else {
int begin = 0, end = LIS.size() - 1;
while(begin <= end) {
int mid = begin + (end - begin) / 2;
if(nums[i] == LIS[mid]) {
begin = mid;
break;
}
if(nums[i] > LIS[mid])
begin = mid + 1;
else
end = mid - 1;
}
LIS[begin] = nums[i];
}
}
return LIS.size();

``````

And the solution for this problem is:

``````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<pair<int, int> > LIS;
sort(envelopes.begin(), envelopes.end(), cmp);
LIS[0] = envelopes[0];
for(int i = 1; i < N; i++) {
if(envelopes[i].second > LIS.back().second)
LIS.push_back(envelopes[i]);
else {
int begin = 0, end = LIS.size() - 1;
while(begin <= end) {
int mid = begin + (end - begin) / 2;
if(envelopes[i].second == LIS[mid].second) {
begin = mid;
break;
}
if(envelopes[i].second > LIS[mid].second)
begin = mid + 1;
else
end = mid - 1;
}
LIS[begin] = envelopes[i];
}
}
return LIS.size();
}
};
``````

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