Simple accepted iterative solution, O(1) space, need help with reducing running time


  • 0
    S

    First I'm gonna show you the solution with stack. The second solution is based on the first one by using two variables indicating the stack's end and top positions.

    Please help with the time-complexity!

    bool verifyPreorder(vector<int>& preorder) {
            if (preorder.size() == 0) return true;
            stack<int> st;
            int minVal = INT_MIN;
            st.push(preorder[0]);
            
            for (int i = 1; i < preorder.size(); i++) {
                if (preorder[i] < minVal) return false;
                if (preorder[i] > preorder[i - 1]) {
                    while (!st.empty() && preorder[i] > st.top()) {
                        minVal = st.top();
                        st.pop();
                    }
                }
                
                st.push(preorder[i]);
            }
            
            return true;
        }
    

    O(1) space

    bool verifyPreorder(vector<int>& preorder) {
            if (preorder.size() == 0) return true;
            int minIndex = -1;
            int top = 0, end = 0;
            
            for (int i = 1; i < preorder.size(); i++) {
                if (minIndex != -1 && preorder[i] < preorder[minIndex]) return false;
                if (preorder[i] > preorder[i - 1]) {
                    while (top >= end && preorder[i] > preorder[top]) {
                        minIndex = top;
                        top--;
                    }
                }
                if (top < end) end = i;
                top = i;
            }
            
            return true;
        }

Log in to reply
 

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