36ms (99.16%) 7-line C++ Solution, O(n) time and O(1) space


  • 0
    K

    The basic idea behind this method is still a stack. The O(1) space complexity is achieved by modifying the preorder vector. Here we keep track of the size of the stack using a variable stk, and for each push/pop operation we modify its value accordingly. Note that it is always safe to replace the value in the preorder vector since it is either the latest value itself or value that we previously popped from the stack.

    bool verifyPreorder(vector<int>& preorder) {
            int pre = INT_MIN, stk = -1, curr = 0;
            while(curr<preorder.size()) {
                while(stk!=-1 && preorder[stk] < preorder[curr]) pre = preorder[stk--];
                if(preorder[curr] < pre) return false;
                preorder[++stk] = preorder[curr++];
            }
            return true;
        }
    

Log in to reply
 

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