438. Check if a Given Sequence Could Be a Valid BST Preorder

Given a sequence of n distinct integers, print 'Yes' if it could be the preorder traversal of some valid binary search tree, otherwise print 'No'.

Input: A single line containing n space-separated distinct integers representing a candidate preorder sequence. Output: Print 'Yes' if the sequence could be a valid BST preorder traversal, otherwise print 'No'.

1 <= n <= 10^5, all values distinct

This is a genuinely clever alternative to actually building the tree - recognizing that a stack combined with a single running lower bound fully captures the BST preorder validity constraint is a great example of finding a leaner, more direct check instead of the 'obvious' construct-and-verify approach.

Check whether a given sequence of numbers COULD be the preorder traversal of some valid binary search tree. Brute force: Actually try to CONSTRUCT a BST from the sequence (using the recursive 'first value is root, split by less-than/greater-than' technique) and check if construction succeeds without contradiction - this works but does more work than the direct stack-based validity check, which never needs to build any actual tree structure. Optimised: The stack-plus-lower-bound technique directly encodes the BST structural constraint (once you've moved past a subtree by popping, everything AFTER must be strictly greater than that subtree's root) without ever constructing an actual tree - a single linear pass with a stack validates the sequence in one shot.

Recursively treat the first element of the current segment as the root, scan forward to find the first element greater than it (the split point between the left and right subtree segments), then verify that every element after that split point is indeed greater than the root, and recurse on the left segment and the right segment. This directly mirrors what a valid BST preorder must look like, but the scan-and-verify step is repeated at every recursive call, so work is duplicated across overlapping ranges. Time: O(n^2) Space: O(n)

Walk through the sequence once with a single index pointer, recursively consuming elements as long as they fall within a valid (low, high) range for the current subtree: the left recursive call uses (low, root value) and the right call uses (root value, high). Because the index only ever moves forward and each element is consumed exactly once, this eliminates the repeated scanning of the brute-force approach while still directly encoding the BST ordering rules. It's correct because a preorder sequence is a valid BST preorder exactly when every value can be placed under some ancestor's bound this way. Time: O(n) Space: O(n)

Iterate through the sequence once while maintaining an explicit stack (representing the current right-spine of ancestors still eligible to be a lower bound) and a running lower bound value. For each new value, first check it isn't smaller than the lower bound (which would violate the BST property); then, while the stack top is smaller than the current value, pop it and raise the lower bound to that popped value, since a smaller node followed by something larger means we've moved into that node's right subtree. Finally push the current value. This is a single linear pass with no recursion overhead at all, using the stack purely as a compact record of valid ancestor bounds. Time: O(n) Space: O(n)

1. Scan the sequence left to right, using a stack and a running lower bound (starting at negative infinity). 2. If the current value is SMALLER than the running lower bound, the sequence is immediately invalid - answer No. 3. While the current value is GREATER than the stack's top, keep popping (each pop means that popped value's entire 'right subtree territory' has just closed off) and raise the lower bound to the last popped value. 4. Push the current value; if the whole sequence is processed without ever violating the lower bound, answer Yes.

Time: O(n) - each value is pushed and popped from the stack at most once across the whole scan. Space: O(n) in the worst case, for the stack.

Test n=1 (trivially valid), a strictly increasing sequence and a strictly decreasing sequence (both valid, purely right- or left-skewed), and n=10^5 for performance with the stack-based approach.

Be ready to explain precisely WHAT popping represents (that a previously-open 'right subtree territory' has now closed, raising the minimum allowed value going forward) - this is the single trickiest insight in an otherwise elegant O(n) technique.