Divide&Conquer Java solution Complexity?


  • 4
    R

    The question is what is time complexity?

    public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head==null) return null;
        if(head.next==null) return new TreeNode(head.val);
        
        ListNode slow = head, fast = head.next;
        while(fast!=null&&fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        
        TreeNode root = new TreeNode(slow.next.val);
        
        
        ListNode second=slow.next.next;
        slow.next=null;
        
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(second);
        
        return root;
    }
    }

  • 0
    Y

    Nice idea! I don't know the time complexity either.


  • 0
    S

    On each recursion level you iterate through entire list 1.5 times with pointers slow and fast. You roughly half the problem size on each recursion call, so recursion depth must be ln(n). So time complexity is n*ln(n). Correct me if I'm wrong.


  • 1
    D

    I think we can write a recursive equation. T(n) = 2T(n/2) + n, then using master theorem to solve this problem. I think it is O(nlogn).


  • 0
    R

    sounds logical. I'll vote for you.


  • 0
    H

    why you set fast as head.next, should fast/slow both start from head to save next.next call.


  • 0
    Z

    Can anyone tell me the space complexity??


  • 1
    S

    Since we end up creating as many tree nodes as there are in the list, I think the space complexity is O(n). Because space complexity is defined as maximum space the program would take in worst case. Correct me if I am wrong.
    But since the depth is logn, I am not sure if the space is O(nlogn) or O(n). Can someone confirm once.
    Thanks.


Log in to reply
 

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