O(n log k)-time, O(k)-space alg. for any increasing k-subsequence


  • 1
    L

    Let us consider the general problem, i.e., determining whether there exists an increasing k-subsequence. This problem is essentially equivalent to finding the Longest Increasing Subsequence. The only difference is that we can just return true if an increasing subsequence of length k is found.

    Below is an O(n log k)-time solution using O(k) space. For this particular problem, k = 3, so the runtime is O(n) and the space is O(1).

    // C++ Code
    bool increasingTriplet(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;
            if (ans.size() >= 3) return true;
        }
        return false;
    }
    

  • 0

    If I wanted k=0, nums=[] to result in true, how would you do it?


  • 0
    L

    Aha, good catch! I would just add an ugly if statement to handle that. :P


  • 0

    I had that trouble in my own one as well and was like "Ah, no, dammit, I don't want to handle that" :-). But then I found a fairly neat fix. It would even make your code slightly shorter...


Log in to reply
 

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