# My way to approach such a problem. How to think about it? Explanation of my think flow.

• I initially solved this problem by "thinking hard", so I came up with a convoluted solution (though greatly simplified when coding): https://leetcode.com/discuss/105584/space-time-elegant-short-clean-solution-detailed-explanation

Today, I revisited this problem. This time, I don't think about how to solve it, instead I want to think about "how to think about it".

Ok, so I read the description again, then I realize, it is asking about some sort of "increasing subsequence" with size 3.

Then I think about all the relevant algorithm I know, for example, the famous "Longest Increasing Subsequence" (LIS) problem.

Then I instantly got a solution: Find the LIS of the input, and if it is greater than 3, return true;
Looks like a working solution, what's its complexity then:

There is a O(nlogk) solution to LIS (if you don't know it, just search this problem in Leetcode and see the discussions), where n is the array length and k is the length of LIS. Here, k is no larger than 2, so it is O(nlog2) = O(n). Very well, a O(n) solution is so easily obtained here:

``````class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
vector<int> dp;
for (auto n : nums)
{
auto iter = lower_bound(begin(dp), end(dp), n);
if (iter == end(dp))
{
dp.push_back(n);
if (dp.size() == 3)
return true;
continue;
}
if (*iter > n)
*iter = n;
}
return false;
}
};
``````

The only difference between LIS and this problem is the check "if (dp.size() == 3)"; For comparison, this is the code to return the LIS of the input nums: You can copy-paste it to the LIS problem and pass it actually.

``````vector<int> dp;
for (auto n : nums)
{
auto iter = lower_bound(begin(dp), end(dp), n);
if (iter == end(dp))
{
dp.push_back(n);
continue;
}
if (*iter > n)
*iter = n;
}
return dp.size();
``````

Apparently, as you may have already noticed, the "dp" here contains at most 2 elements, so one instant simplification here is to replace "lower_bound" call to a simple "if comparison else comparison". Then a much more simplified version is obtained:

``````class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int a = INT_MAX, b = INT_MAX;
for (auto n : nums)
if (n <= a)
a = n;
else if (n <= b)
b = n;
else
return true;
return false;
}
};
``````

You may have seen 100 ways to explain why this "if .. else" works in other discussions. Here, it is so easy to understand: it is just a simple version of Binary Search for 2 elements -- the replacement of lower_bound in above solution.

Following this think flow, I managed to come up with this elegant solution without any "hard thinking".

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