Verify Preorder Sequence in Binary Search Tree

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Consider the following binary search tree:

     5
    / \
   2   6
  / \
 1   3

Example 1:

Input: [5,2,6,1,3]
Output: false

Example 2:

Input: [5,2,1,3,6]
Output: true

Follow up: Could you do it using only constant space complexity?

o(n) time and space

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if(preorder == null || preorder.length == 0)
            return true;
        
        Stack<Integer> stack = new Stack<>();
        int low = Integer.MIN_VALUE;
        
        for(int p : preorder){
            if( p < low){
                return false;
            }
            
            while(!stack.isEmpty() && p > stack.peek()){
                low = stack.pop();
            }
            
            stack.push(p);
        }
        
        return true;
    }
}

time on, space o1

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if(preorder == null || preorder.length == 0)
            return true;
        
        int low = Integer.MIN_VALUE, i = -1;
        
        for(int p : preorder){
            if(p < low){
                return false;
            }
            
            while( i >= 0 && p > preorder[i]){
                low = preorder[i--];
            }
            
            preorder[++i] = p;
        }
        
        return true;
    }
}