O(n) time O(n) space Java solution using Stack. (13ms)


  • 1
    2
    public class Solution {
        public boolean find132pattern(int[] nums) {
    	if (nums.length <= 2) {
    	    return false;
    	}
           	Stack<Point> points = new Stack<Point>();
    	Point now = new Point(nums[0], nums[0]);
    	for (int num : nums) {
    	    if (num < now.x) {
    		points.add(now);
    		now = new Point(num, num);
    	    } else if (num > now.y) {
    		while (points.size() > 0 && points.peek().y <= num) {
    	           points.pop();
    		}
    		if (points.size() > 0 && points.peek().x < num) {
    		   return true;
    		}
    		now.y = num;
    	   } else if (now.x < num && now.y > num) {
    		return true;
    	   }
    	}
    	return false;
        }
    }
    

  • 0
    O

    for your information:

    Point.x = the minimum value till current iteration node
    Point.y = the maximum value that appears after Point.x till current iteration node


Log in to reply
 

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