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

• 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.

``````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;
}``````

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