O(n) time complexity and O(1) space complexity solution without using two-pointers


  • 1
    A

    Two-pointer solutions require O (n lg n) time complexity since in each recursion, the function fully scans its range of the array.

    First find the length of the linked list (O(n)), then create the balanced binary search tree by limiting the indexes below the capacity and meanwhile insert the values into the tree (Another O(n)).

    Update explanation as requested by chuanyu526:

    You could imagine an index number for each node on the binary tree as on this reference:
    http://www.cse.hut.fi/en/research/SVG/TRAKLA2/tutorials/heap_tutorial/taulukkona.html

    The elements are labeled 1, (2,3), (4,5,6,7), (...) on each layer.
    A parent with label n will have children (left 2 * n) and (right 2 * n + 1).

    The capacity of the tree would be the length of the linked list l. Then the last element's index will be l, and any children with index > l will not be created.

    The tree creation could be done in-order, and value assignment from the linked list can also be done in-order during the node creation.

    Therefore the time complexity is O(n) and no additional space is required.

        public TreeNode sortedListToBST(ListNode head) {
        // 1st pass: find the length
        int count = 0;
        ListNode chead = head;
        while (chead != null) {
            count ++;
            chead = chead.next;
        }
        // 2nd pass: create tree recursively for the given length, and fill in values in-order
        TreeNode root = createNodes (1, count, new ListNode[] {head});
        return root;
    }
    
    public TreeNode createNodes (int index, int capacity, ListNode[] listNode) {
        if (index > capacity) {
            return null;
        }
        TreeNode root = new TreeNode (0);
        root.left = createNodes (index * 2, capacity, listNode);
        root.val  = listNode[0].val;
        listNode[0] = listNode[0].next;
        root.right = createNodes (index * 2 + 1, capacity, listNode);
        return root;
    }
    

    The submission returns 1 ms on the (32 / 32) case set (beats 45.82%), which the O ( n lg n) also does (I wonder why)

    But one interesting case is the list with all numbers between -999 and 15340, which neither my solution nor a two-pointer solution (such as this one https://leetcode.com/discuss/58428/recursive-construction-using-slow-fast-traversal-linked-list) could pass (TLE). Any comments would be appreciated. Correct me for any mistakes.


  • 0
    F

    Can you explain a little more on how it works?


  • 3
    Y

    But the recursion will use the stack space, so your code should be using O(log n) space.

    Also, the performance difference between O(n log n) and O(n) could be hardly seen by the runtime (when n=2^32, log n=32, you can consider it as a constant).


Log in to reply
 

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