Strict O(1) space solution without using stack, without modifying preorder array


  • 1
    O

    Each time when you encounter a preorder[i] > preorder[i - 1], you know you are going to right branch, and you need to update the min boundary for that right sub tree. The min boundary is the local parent of that right sub tree, the value is indeed equals to the largest preorder element among [0 ~ i - 1] while smaller than preorder[i].

    public class Solution {
        public boolean verifyPreorder(int[] preorder) {
            int min = Integer.MIN_VALUE, n = preorder.length, j, i, k;
            for (i = 1; i < n && preorder[i] > min; i++) 
                if (preorder[i - 1] < preorder[i]) {
                    for (k = i - 1, j = i - 2; j >= 0; j--)
                        if (preorder[j] < preorder[i] && preorder[j] > preorder[k]) k = j;
                    min = preorder[k]; 
                }
            return i >= n;
        }
    }

  • 0
    K

    Nice idea :) This is fast enough for Java but the equivalent C++ code will yield Time Limit Exceeded for any large test case where the given sequence has strictly increasing order like:

    [1, 2, 3, 4, 5,........., 4999, 5000, 50001, .........., 7998, 7999, 8000]
    

    Because every-time the finding local parent loop will hit at the root of the tree. So it will become an O(n^2) algorithm. One possible pruning is - keep track the last local parent index. As a result, we don't need to search local parent for further nodes above the previous node's local parent.

    class Solution {
    public:
        bool verifyPreorder(vector<int>& preorder) {
            if(preorder.empty()) return true;
            
            int Min = INT_MIN;
            int n = (int)preorder.size();
            int i = 0, minIndx = -1;
            for(i = 1; i < n and preorder[i] > Min; ++i) {
                if(preorder[i] > preorder[i - 1]) {
                    int k = i - 1;
                    for(int j = i - 2; j > minIndx; --j) {
                        if(preorder[j] < preorder[i] and preorder[j] > preorder[k]) {
                            k = j;
                        }
                    }
                    minIndx = k;
                    Min = preorder[k];
                }
            }
            return (i >= n); 
        }
    };
    

    This solution will now run within time limit :)


  • 0
    S

    Run this case[12,8,2,3,7,4,5,9,6]


Log in to reply
 

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