Idea: Keep a max and min. Once you see a max. then update your min to existing max and max to new max. Any value at any time should be between min and max.

Main problem here is finding the minimum (assuming there can be negative numbers).

Assume first element is the minimum. Then go through the array till we see first non-decreasing element.

That's the min we will use.

```
class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
if(preorder.size()==0) return true;
int maxVal = preorder[0];
int minVal = preorder[0];
// go through the till you find the an element which is greater than previous
// Example: 3,2,1,4 . In this case that element is 4. So we stop at 4
our minima is 1
for ( int i=0; i < preorder.size(); i++ ) {
if(i > 0 && preorder[i] > preorder[i-1]) break;
minVal = min(minVal, preorder[i]);
}
//
// Go through the array second time
for ( int i=0; i < preorder.size(); i++ ) {
if ( preorder[i] < minVal) {
// If current value is less than min.. this is not possible
return false;
}
if ( preorder[i] > maxVal ) {
minVal = maxVal;
maxVal = preorder[i];
}
}
return true;
}
};
```