Time Limit Exceeded on submission, but passed on Run code


  • 0
    K

    I wrote a recursive solution which is not of constant space complexity but I hoped it will be fast enough to be passed.

    class Solution {
        bool verifyPreorder(int left, int right, vector<int> const& preorder) {
            if(left >= right) { return true; }
            
            int root = preorder[left];
            int leftIndx = left + 1, rightIndx = right + 1;
            for(int k = left + 1; k <= right; ++k) {
                if(preorder[k] > root) {
                    rightIndx = k;
                    break;
                }
            }
            for(int k = rightIndx; k <= right; ++k) {
                if(preorder[k] < root) {
                    return false;
                }
            }
            
            return verifyPreorder(left + 1, rightIndx - 1, preorder) and verifyPreorder(rightIndx, right, preorder);
        }
        
    public:
        bool verifyPreorder(vector<int>& preorder) {
            if(preorder.empty()) return true;
            return verifyPreorder(0, (int)preorder.size() - 1, preorder);
        }
    };
    

    But when I submitted pressing Submit Solution, the OJ yielded Time Limit Exceeded for below test case (brief):

    [8000,7999,7998,7997,7996,7995,7994,7993,7992,7991,7990,7989,7988,7987,7986,7985,7984,7983,7982,7981,7980,7979,7978,............................. ....... .........,13,12,11,10,9,8,7,6,5,4,3,2,1]
    

    Then I tried this as custom testcase and the code ran within time and took 152ms. Is this time too much? Is the tester program different for OJ and testing code?

    Thanks in advance!


  • 0
    K

    It seems the recursion based solution was not fast enough for OJ. So I took some idea from some threads and ended up writing stack based O(n) space solution and another constant space solution.

    class Solution {
        bool verifyPreorder(int left, int right, vector<int> const& preorder) {
            if(left >= right) { return true; }
            
            int root = preorder[left];
            int leftIndx = left + 1, rightIndx = right + 1;
            for(int k = left + 1; k <= right; ++k) {
                if(preorder[k] > root) {
                    rightIndx = k;
                    break;
                }
            }
            for(int k = rightIndx; k <= right; ++k) {
                if(preorder[k] < root) {
                    return false;
                }
            }
            
            return verifyPreorder(left + 1, rightIndx - 1, preorder) and verifyPreorder(rightIndx, right, preorder);
        }
        
    public:
        bool verifyPreorder(vector<int>& preorder) {
            if(preorder.empty()) return true;
            
            // TLE
            // return verifyPreorder(0, (int)preorder.size() - 1, preorder);
            
            // O(n) stack based solution
            /*
            int Min = INT_MIN;
            int n = (int)preorder.size();
            stack<int> stk;
            stk.push(preorder[0]);
            
            for(int i = 1; i < n; ++i) {
                if(preorder[i] < Min) return false;
                while(!stk.empty() and preorder[i] > stk.top()) {
                    Min = stk.top();
                    stk.pop();
                }
                stk.push(preorder[i]);
            }
            
            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]) { // we entered in right branch
                    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); 
        }
    };

Log in to reply
 

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