Two solutions in C++, well-explained


  • 6

    Solutions

    DP

    It's quite intuitive to adopt DP to solve this problem:

    • sorting the envelopes first via its first value (width)
    • allocating an array to record the maximal amount for each envelope (the maximal amount we can get ending with the current envelope)

    Directly the time cost here will be o(nlogn+n^2) which is o(n^2) and meantime taking up o(n) extra space.

    int maxenvelopes(vector<pair<int, int>>& envelopes) 
    {
    	int size = envelopes.size();
    	if(!size) return 0;
    	sort(envelopes.begin(), envelopes.end());
    	int maxrolls[size]{0}, maxroll = 1;
    	maxrolls[0] = 1;
    	for(int i = 1; i < size; ++i)
    	{
    		maxrolls[i] = 1;
    		for(int j = i-1; j >= 0; --j)
    			if(envelopes[i].first>envelopes[j].first && envelopes[i].second>envelopes[j].second)
    				maxrolls[i] = max(maxrolls[i], maxrolls[j]+1);
    		maxroll = max(maxroll, maxrolls[i]);
    	}
    	return maxroll;
    }
    

    LIS

    Actually here we are counting the longest increasing sequence as well except there are two dimensions we need to consider. And also we should remember the o(nlogn) solution in LIS, where the essential greedy concept is trying to

    1. make the all the elements in the collector as small as possible, especially the last one which is the gate to control the size of the collector - the longest length;
    2. append the bigger ones to the collector;

    But here we need to make some modifications since there are two dimensions to consider. To ensure the two dimensions array can be compressed into one dimension and meantime the requirements of the two conditions above are also properly met, just sorting is not enough here.

    • we need to convert this 2-dimentsion problem to a 1-dimension LIS: first sort the array via the width in ascending order and then sort the sub-array with the same width in descending order (the height) then the two conditions in LIS will also be met traversing from the smallest width to the biggest: and the height will be used as that in LIS - the last element will be updated to be as smaller as possible and meantime maintain the envelopes constraint since its width order will always be valid, furthermore the condition 2 is also met just as that in LIS.

    Note if we do not sort the sub-arrays (with the same width) in descending order, the LIS in the height is then invalid. Suppose the sub-arrays are also sorted in ascending order, the height in the same width will be appended in our LIS method, wrong result. To sort the heights in the same width in descending order will avoid this case by updating the height in the same width since we are using lower_bound.

    Time complexity now becomes O(nlogn) taking up O(n) space.

    int maxEnvelopes(vector<pair<int, int>>& envelopes) 
    {
    	int size = envelopes.size();
    	sort(envelopes.begin(), envelopes.end(), [](pair<int, int> a, pair<int, int>b){
    		return a.first<b.first || (a.first==b.first && a.second>b.second);
    	});
    	vector<int> collector;
    	for(auto& pair: envelopes)
    	{
    		auto iter = lower_bound(collector.begin(), collector.end(), pair.second);
    		if(iter == collector.end()) collector.push_back(pair.second);
    		else if(*iter > pair.second) *iter = pair.second;
    	}
    	return collector.size();
    }
    
    lower_bound
    • On random-access iterators, logarithmic in the distance between first and last: Performs approximately log2(N)+1 element comparisons (where N is this distance).
    • On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.
      Always welcome new ideas and practical tricks, just leave them in the comments!

  • 0
    T

    Very nice solution with the LIS method!


  • 1

    @r3d33m basically 2 reasons:

    1. once you found one with lower height using lower_bound, it is guaranteed to also have a smaller width.
    2. once you found one with higher or equal height, it is safe to update height with current one. for example [1,6], [2,4],
      first 6 into vec,
      then replaced with 4 without care that 1 < 2 since if there is [2, 8], that will appear before [2,4]. the next one that can wrap [1,6] will definitely be able to wrap [2,4]

Log in to reply
 

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