5 lines O(n log n) C++ solution


  • 3
    L

    Like most ACed solutions, we can use Binary Search to speed up the original O(n^2) DP solution.

    // C++ Code
    int lengthOfLIS(vector<int>& nums) {
        vector<int> ans;
        for (int a : nums)
            if (ans.size() == 0 || a > ans.back()) ans.push_back(a);
            else *lower_bound(ans.begin(), ans.end(), a) = a;
        return ans.size();
    }
    

    Runtime = O(n log n).


  • 0
    P

    please explain it


  • 0
    T

    Very tricky!


  • 0
    L

    Yeah, the trick here is that *lower_bound() can be used as an lvalue.


  • 3
    E

    This is a beautiful solution!

    ans[i] maintains the smallest ending integer, among all ascending subsequence with length of i. Once I realize this, the algorithm becomes crystally clear.


  • 0
    L

    You are right, and I am glad you like it. :)


  • 1
    V

    Do note that if, as a followup, you were asked to return the actual vector containing the minimum subsequence, you can't just return ans:

    e.g.

    2 3 7 9 5
    

    ans will replace 7 with 5 and thus return

    2 3 5 9
    

    whereas the correct solution is

    2 3 7 9
    

    however, the lengths of the optimal solution and our current solution will be the same!


  • 0
    N

    cool algorithm


Log in to reply
 

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