132 Pattern Solution Java


  • 0
    static class Interval {
    	int start;
    	int end;
    	public Interval(int start, int end) {
    		this.start = start;
    		this.end = end;
    	}
    	public String toString() {
    		return this.start+","+this.end;
    	}
    }
    public boolean find132pattern(int[] nums) {
    	if(nums==null || nums.length<3) 
    		return false;
    	Set<Interval> intervals = new HashSet<>();
    	int max = nums[0];
    	int min = nums[0];
    	Interval currentInterval = new Interval(min,max);
    	for(int i=0;i<nums.length;i++) {
    		int n = nums[i];
    		if(n<min) {
    			intervals.add(currentInterval);
    			min = n;
    			max = n;
    			currentInterval = new Interval(min, max);
    		}
    		if(n>max) {
    			max = n;
    			currentInterval.end=max;
    		}
    		if(n>currentInterval.start && n<currentInterval.end) {
    			return true;
    		}
    		for(Interval interval: intervals) {
    			if(n>interval.start && n<interval.end) {
    				return true;
    			}
    		}
    	}
    	return false;
    }
    
    1. Keep track of the min and max elements found in the current Interval.
    2. If a new min is found, store the current interval in a set and generate a new Interval.
    3. If the current element is contained in the current interval, or in any interval previously found, return true.

Log in to reply
 

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