Java O(n) time O(n) space but not that brilliant solution


  • 0
    C

    Compared to those brilliant O(n) time O(1) space solution, this solution is easy to understand.
    I introduced two array, one array to keep the min value from 0 to j so far, and the other array keep the max value from j too len-1. If we found any j, it meets min[j] < nums[j] < max[j], then we found it.

    class Solution {
        public boolean increasingTriplet(int[] nums) {
            if (nums==null || nums.length<3)
                return false;
            
            int len = nums.length;
            // leftMin keep a min value between 0..j
            // rightMax keep a max value between j..len-1
            // found it if leftMin[j] < nums[j] && rightMax[j] > nums[j]
            int[] leftMin = new int[len];        
            int[] rightMax = new int[len];
            
            leftMin[0] = nums[0];
            for (int i=1; i<len; i++)
            {
                leftMin[i] = Math.min(nums[i], leftMin[i-1]);
            }
            
            rightMax[len-1] = nums[len-1];
            for (int k=len-2; k>=0; k--)
            {
                rightMax[k] = Math.max(nums[k], rightMax[k+1]);
            }
            
            for (int j=1; j<len-1; j++)
            {
                if (leftMin[j] < nums[j] && rightMax[j] > nums[j])
                    return true;
            }
            return false;
        }
    }
    

Log in to reply
 

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