Generalized solution


  • 0
    L

    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.


Log in to reply
 

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