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

  • 3

    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

    please explain it

  • 0

    Very tricky!

  • 0

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

  • 3

    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

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

  • 1

    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:


    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

    cool algorithm

Log in to reply

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