# Generalized solution

• Idea from Longest Increasing Sequence - LIS

Similar problem, I'm using similar solution.

LIS is solved by using patience sorting - O(nlgn)

Thus, the number of increasing items is the number of piles formed at the end, which is just LIS

actual code posted

``````public boolean increasingTriplet( int[] nums )
{
if ( nums.length == 0 )
return false;
int[] stack = new int[nums.length];
stack[0] = nums[0];
int count = 1, left = 0, right = count, mid = ( left + right ) / 2;
for ( int i = 1; i < nums.length; i++ )
{
left = 0;
right = count - 1;

// binary search for position where nums[i] to be inserted
while ( left < right - 1 )
{
if ( nums[i] < stack[mid] )
right = mid;
else
left = mid;
mid = ( left + right ) / 2;
}
// now nums[i] is between left and right
if ( stack[left] >= nums[i] )
stack[left] = nums[i];
else
{
if ( stack[right] >= nums[i] )
stack[right] = nums[i];
else
{
stack[right + 1] = nums[i];

if ( right + 1 == count )
count++;
}
}
//System.out.println( Arrays.toString( stack ) + "\t" + count );
}
return count < 3 ? false : true;
}
``````

On last line, the value '3' is set by the problem.

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