<p>Given an integer array <code>nums</code>, return <code>true</code><em> if there exists a triple of indices </em><code>(i, j, k)</code><em> such that </em><code>i &lt; j &lt; k</code><em> and </em><code>nums[i] &lt; nums[j] &lt; nums[k]</code>. If no such indices exists, return <code>false</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5]
<strong>Output:</strong> true
<strong>Explanation:</strong> Any triplet where i &lt; j &lt; k is valid.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,4,3,2,1]
<strong>Output:</strong> false
<strong>Explanation:</strong> No triplet exists.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,1,5,0,4,6]
<strong>Output:</strong> true
<strong>Explanation:</strong> The triplet (3, 4, 5) is valid because nums[3] == 0 &lt; nums[4] == 4 &lt; nums[5] == 6.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 5 * 10<sup>5</sup></code></li>
	<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

<p>&nbsp;</p>
<strong>Follow up:</strong> Could you implement a solution that runs in <code>O(n)</code> time complexity and <code>O(1)</code> space complexity?
class Solution {
public:
	vector<int> findSequence(int iter, vector<int>& nums) {
		vector <int> passed;
		passed.reserve(nums.size());
		int len = nums.size();
		int mx[len];
		mx[len-1] = INT_MIN;

		for (int i = len-2; i >= 0; i--) {
			mx[i] = max(mx[i+1], nums[i+1]);
			if (nums[i] >= mx[i]) {
				mx[i] = INT_MIN;
			}
			if (mx[i] != INT_MIN) {
				// cout << "ITER:" << iter << " => " << nums[i] << " m:" << mx[i] << endl;
				passed.push_back(nums[i]);
			}
		}

		// cout << "ITER:" << iter << " => ";
		// for (auto x : passed) {
		// 	cout << x << " ";
		// }
		// cout << endl;

		reverse(passed.begin(), passed.end());
		return passed;
	}

	bool increasingTriplet(vector<int>& nums) {
		// [1, 2, 3, 4, 5]
		// 2 mins that min[i] < min[j] so that i < j
		// [1,     2,     3,     4,    5]
		//  1, 2   2, 3   3, 4   4,5   5
		// [5, 4, 3, 4, 1, 6, 10]
		// [ 100, 2,   4,   105, 1,   10]
		// [ YES, YES, YES, NO,  YES, NO]
		// 100 -> 103 ? > 103 O(n^2 * logN)
		
		bool answer = false;
		auto first = findSequence(1, nums);

		if (first.size() < 2) {
			return false;
		}

		auto second = findSequence(2, first);
		return second.size() > 0;
	}
};
122900