Java Solution improvement without modifying the original array


  • 0
     public boolean verifyPreorder(int[] preorder) {
            if(preorder.length==0) return true;
            Stack<Integer> stack=new Stack<Integer>();
            stack.push(preorder[0]);
            int leftBound=Integer.MIN_VALUE;
            for(int i=1;i<preorder.length;i++)
            {
              //  System.out.println(stack);
                if(preorder[i]<stack.peek())
                {
                    if(preorder[i]<leftBound) return false;
                    //sink
                     stack.push(preorder[i]);
                }
                else{
                    //swim
                   while(!stack.isEmpty() &&stack.peek()<preorder[i])
                   {
                     leftBound=stack.pop();
                   }
                   stack.push(preorder[i]);
                }
            }
            return true;
        }
    

    This is the native Stack version. The complexity is O(N) and space is O(N)

    If you want to reduce the space from O(N) to O(1) without modifying the original array.
    You must sacrifice the time.
    I will say worst case is O(N2)
    Here is the O(1) space version. Same idea just traversing all the previous array instead of removing the top element in the stack.

    public class Solution {
        public boolean verifyPreorder(int[] preorder) {
            if(preorder.length==0) return true;
            int lastPos=0;
            int leftBound=Integer.MIN_VALUE;
            for(int i=1;i<preorder.length;i++)
            {
              //  System.out.println(stack);
                if(preorder[i]<preorder[lastPos])
                {
                    if(preorder[i]<leftBound) return false;
                    //sink
                     lastPos=i;
                }
                else{
                    //swim
                    for(int k=lastPos;k>=0;k--)
                    {
                        if(preorder[k]>preorder[i]) break;
                        leftBound=Math.max(leftBound,preorder[k]);
                    }
                  lastPos=i;
                }
            }
            return true;
        }
        
    }
    

Log in to reply
 

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