Clean java solution O(n)


  • 0
    A
    public boolean find132pattern(int[] nums) {
    	Stack<Range> stack = new Stack<>();
    	for(int num : nums) {
    		Range cur = new Range(num, num);
    		while(!stack.isEmpty() && cur.max > stack.peek().min) {
    			cur.min = Math.min(stack.peek().min, cur.min);
    			cur.max = Math.max(stack.peek().max, cur.max);
    			stack.pop();
    		}
    		stack.push(cur);
    		
    		if(stack.peek().min < num && num < stack.peek().max)
    			return true;
    	}
    	
    	return false;
    }
    
    public static class Range {
    	public int min;
    	public int max;
    	
    	public Range(int mn, int mx) {
    		min = mn;
    		max = mx;
    	}
    }
    
    Time complexity:  O(n)
    Space complexity: O(n)

  • 0
    S

    O(N^2) should not be allowed to pass this problem. Or the problem should be rejudged.


  • 0
    A

    @hamster Agree. Added O(n) solution using stack.


Log in to reply
 

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