Java NLogN Solution with Explanation


  • 205
    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]

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

  • 14
    W

    clever solution, here is my C++ version

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

  • 0
    G

    I think you forget to remove the vector candidates


  • 20
    A

    "descend on height if width are same" - this is just brilliant!!


  • 0
    H

    very nice solution!


  • 2
    S

    Brilliant and easy to understand. I tried to solve it with DFS but it exceeds the time limit haha.


  • 6
    T

    What a concise and comprehensive explanation!

    Here is my Python code following your thought:

    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

  • 0

    Ah, I forgot the hi parameter. My version using it:

    def maxEnvelopes(self, envelopes):
        end = [None] * len(envelopes)
        hi = 0
        for _, h in sorted(envelopes, key=lambda (w, h): (w, -h)):
            i = bisect.bisect_left(end, h, hi=hi)
            end[i] = h
            hi += i == hi
        return hi

  • 0
    W

    great, thanks!


  • 0

    Really smart ideas to increase for width and decrease for height


  • 0
    A

    Genius idea!!


  • 0
    R

    Still not understand why LIS would solve the problem. Could you please elaborate more on your thought process? thanks.


  • 1
    A

    Every subsequence will have widths in increasing order. Every increasing subsequence, additionally, will have heights in increasing order as well (for computing increasing subsequences, we only see the heights). The reversing takes care of some cases that we should not return like (4,6) and (4,7). Try it with an example


  • 0
    T

    If we extend the problem to 3d (a set of boxes with height, width and length), I am wondering if it is possible to formulate a similar simple solution. Thoughts?


  • -1
    M

    I tried DFS and exceeded the time limit. Seems this is the best solution.


  • 0
    F

    can anyone help to explain that how it avoid envelops with same width? Thanks!


  • 0
    S
    This post is deleted!

  • 0
    X
    This post is deleted!

  • -1
    A

    Explanation is not very clear but even if it was detailed it would be impossible to understand without first getting the sense of "Longest Increasing Subsequence" tricky O(nlgn) solution. I personally managed to solve leetcode task using recursion + DP + many optimizations to decrease the number of operations (like jumping over envelopes forward the sorted array etc). But anyway it was so slow that took 800 ms in to run in overall and the result was somewhat 0.45% of others performance :D

    So indeed this is a really awsome solution to the problem


  • 0
    L

    The way you deal with envelope that has same width is great!


Log in to reply
 

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