255. Verify Preorder Sequence in Binary Search Tree - Explanation

Problem Link

Description

Given an array of unique integers preorder, return true if it is the correct preorder traversal sequence of a binary search tree.

Example 1:

Input: preorder = [5,2,1,3,6]

Output: true

Example 2:

Input: preorder = [5,2,6,1,3]

Output: false

Constraints:

• 1 <= preorder.length <= 10⁴
• 1 <= preorder[i] <= 10⁴
• All the elements of preorder are unique.

Follow up: Could you do it using only constant space complexity?

Company Tags

Salesforce3 NVIDIA2 Zenefits2

1. Monotonic Stack

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        min_limit = float('-inf')
        stack = []
        
        for num in preorder:
            while stack and stack[-1] < num:
                min_limit = stack.pop()
                
            if num <= min_limit:
                return False
            
            stack.append(num)
        
        return True

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the length of preorder

---

2. Constant Auxiliary Space

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        min_limit = float('-inf') 
        i = 0
        
        for num in preorder:
            while i > 0 and preorder[i - 1] < num:
                min_limit = preorder[i - 1]
                i -= 1
                
            if num <= min_limit:
                return False
            
            preorder[i] = num
            i += 1
        
        return True

Time & Space Complexity

• Time complexity: $O(n)$

• Space complexity: $O(1)$ auxiliary

  • A common misconception is that modifying an input array for use in an algorithm leads to an $O(1)$ space complexity. In reality, you are still using $O(n)$ space, but $O(1)$ auxiliary space.

  • Because we are modifying the input to directly use in the algorithm, we must count it as part of the space complexity. However, we are not using any auxiliary space other than a few integers.
    The exception to this is in-place algorithms where the input is also returned as the output. For example: sorting algorithms.

Where $n$ is the length of preorder

---

3. Recursion

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        def helper(i, min_limit, max_limit):
            if i[0] == len(preorder):
                return True
            
            root = preorder[i[0]]
            if not min_limit < root < max_limit:
                return False

            i[0] += 1
            left = helper(i, min_limit, root)
            right = helper(i, root, max_limit)
            return left or right
            
        return helper([0], float('-inf'), float('inf'))

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the length of preorder