An elegent O(n) time complexity and O(1) space complexity Algorithm


  • 8
    R

    Note: 1. Given a sequence {1, 4, 3, 7, 9}, you find pair 4(!<=)3, swap this pair and sequence is in order.
             2. Given a sequence {1, 9, 4, 5, 3, 10}, you get first pair 9(!<=)4 and second pair 5(!<=)3, swap pair 9(!<=)3 and sequence is in order.
             3. Given a sequence, only in two above (general) cases, that you can just swap one pair numbers to convert an unordered sequence into ordered.
             4. You can tranverse BST inorder to get above sequence.
    So, my alg is:

    void recover(TreeNode *root, TreeNode *&pre, TreeNode *&a, TreeNode *&b) {
        if (root)
        {
            recover(root->left, pre, a, b);
            
            if (root->val < pre->val)
            {
                if (!a) a = pre; //a should change once.
                b = root; //b could change twice.
            }
            pre = root;
            
            recover(root->right, pre, a, b);
        }
    }
    void recoverTree(TreeNode *root) {
        if (!root) return;
        
        TreeNode p(numeric_limits<int>::min());
        TreeNode *a, *b, *pre;
        a = b = 0;
        pre = &p;
        recover(root, pre, a, b);
        if (a && b)
        {
            swap(a->val, b->val);
        }
        return;
    }
    

    I think this problem requirement is strange. Does O(1) space complexity algorithm exists?

         1. Does BST should be tranversed?
         2. If answer of 1 is true, I don't think an O(1) space complexity exists, for there does not exists a BST tranverse algorithm taking O(1) space complexity.
        3. If answer of 1 is false, I just wonder how can you find the disordered pair.


  • 1
    M

    I think the space complexity is O(lgn) (worst case O(n)) if you use recursion. Is that right?


  • 2
    R

    I do not think the algorithm meet the requirements of the problem. It's not O(1). It is the straightforward solution mentioned in the problem discription


  • 1
    W

    recursion is never O(1)


  • 4
    S

    I think yours is a pretty nice one, and the O(n) approach mentioned in the description likely refers to traversal with explicit stack. In case you really wonder if there is BST traversal algo with O(1) space complexity, you might wanna read the answer for this question.


  • 11
    L
    // morris traversal
    /******************************************************************************************/
    /* Inorder Traversal(should get ascending seq.):Analysis:
    case A: If 2 near nodes swapped,then there will be just 1 Inversion Pair.
    case B: If 2 nodes not near swapped,then there will be 2 Inversion Pairs.
    Weather case A or case B, swap the max-value and the min-value of the Inversion Pair(s).*/
    /*****************************************************************************************/
    class Solution {
    public:
    void recoverTree(TreeNode *root) {
        TreeNode *cur, *pre, *node1, *node2;  // node1, node2: Record 2 near nodes
        TreeNode *first, *second;  // Record 2 swapping nodes
        node1 = node2 = first = NULL;
        cur = root;
        while(cur) {
            if(cur->left == NULL) {
                if(node1 == NULL) node1 = cur;
                else if(node2 == NULL) node2 = cur;
                else { node1 = node2; node2 = cur;}
                cur = cur->right;
            } else {
                pre = cur->left;
                while(pre->right && pre->right != cur) pre = pre->right;
                if(pre->right == NULL) {
                    pre->right = cur;
                    cur = cur->left;
                    continue;
                } else {
                    pre->right = NULL;
                    if(node2 == NULL) node2 = cur;
                    else {node1 = node2; node2 = cur;}
                    cur = cur->right;
                }
            }
            if(node1 && node2 && node1->val > node2->val) {
        
                if(first == NULL)  first = node1;
                second = node2;
            }
        }
        /* already learn that there exist 2 nodes swapped.*/
        int t = first->val;
        first->val = second->val;
        second->val = t;
    }
    };
    

    O(1) space Solution.
    No need thanks.


  • 0
    L

    yeah, the recursion itself cost O(n).


  • 0
    L

    However, when it comes to morris method, the structure of this BST has changed.


  • 0
    Z

    I think this solution meet the requirement of the problem. The straightforward solution in the description is storing all the values in O(n) space and then find two invalid values.


  • 0
    R
    This post is deleted!

  • 0
    L

    We just make a use of the structure of the BST. But there is no change on the structure of BST when we traverse it over.
    If you have any doubt, you can do several traversals to this BST with Morris Method.


  • 0
    I

    I like your solution, it's very readable and easy understanding


  • 0
    Z

    Question: if (!a) a = pre; b = root; Could someone please explain more about how this works? Thanks!


  • 0
    H

    First translate BST into a list, and then do the magic. Good idea!


  • 0
    E

    @zhi.huang: However what the question is really asking is a constant space solution. No recursive solution could meet this requirement. I think using Morris traversal is the only way.


  • 0
    Q

    you can get O(1) space with moris mid order traversal


  • 0
    J
    This post is deleted!

  • 0
    J
    This post is deleted!

  • 0
    Y

    You are right, but the solution is extremely tricky


  • 0
    B

    Thx.. Do you know where I can find reference on space complexity on recursion ?


Log in to reply
 

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