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

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

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

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

• 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...

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