TLE for an O(nlgn) solution


  • 0
    K

    The complexity of following code is nlgn, but still have the TLE.

    Anyway to improve it?

    Look for help

    /**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        public ListNode sortList(ListNode head) {
    		if(head == null || head.next == null)
    			return head;
    		ListNode end = head;
    		while(end.next!= null){
    			end = end.next;
    		}
    		
    		ListNode sorted = mergeSort(head,end);
    		return sorted;
    	}
        
        public ListNode mergeSort(ListNode start, ListNode end) {
    
            //condition to terminate the recurrsion
    		if(start == end)
    			return start;
    		
    		ListNode current = start;
    		ListNode middle = start;
    
    		while (current!=null && current.next!=null && current.next.next != null) {
    		    middle = current.next;
    			current = current.next.next;
    		}
    		
    		ListNode middleNext = middle.next;
    		middle.next = null;
    		end.next = null;
    		
    		//break the long list to two indivadual linkedlists.
    		ListNode left = mergeSort(start, middle);
    		ListNode right = mergeSort(middleNext, end);
    
    		return merge(left, right);
    
    	}
    
    	public ListNode merge(ListNode start, ListNode middle) {
    		ListNode a = start;
    		ListNode b = middle;
    
    		ListNode helper = new ListNode(0);
    
    		while (true) {
    			if (a == null) {
    			    //apend the rest of second list to the end of helper
    				helper.next = b;
    				break;
    			}
    			if (b == null) {
    				//apend the rest of first list to the end of helper
    				helper.next = a;
    				break;
    			}
    
    			if (a.val > b.val) {
    				helper.next = b;
    				b = b.next;
    			} else {
    				helper.next = a;
    				a = a.next;
    			}
    			helper = helper.next;
    		}
    
    		return helper.next;
    	}
    	
        }

  • 0
    L

    I am not sure the merge function is correct. Why return helper.next? Have you tried it with small examples? Sorry if I am wrong.


  • 0
    M

    I believe the attempt is adding a node to the start, then putting the output onto it. That way, helper.next would be the first node added to the list. However, the current merge() has helper advance as well, so helper.next as returned will be the last node added. In other words, it will be the lowest value greater than all terms in the other list, not the sorted list as expected.

    To fix merge, maybe add:
    ListNode temp = helper;
    just after helper is created, and then
    return temp.next
    at the end.


  • 1
    M

    Your problem here is that, while merge sort is O(nlogn), this is not. Merge sort is able to get the middle of a list in O(1) time, since arrays have constant time random access, but a linked list will take O(n) time to get there. Therefore, a linked list merge sort in this fashion will take O(n*nlogn).

    You are on the right track, but you need some way of either getting the middle in O(1), or not needing the middle at all. On the other hand, a top-down recursive method for mergesort will use O(logn) space on the stack, so won't pass the constant space part of the challenge. I suggest looking for other methods of doing merge sort to see if you can avoid these problems.

    EDIT My mistake. However, it turns out the implementation isn't quite right. Looking back over mergesort, you have this while loop:

    while (current!=null && current.next!=null && current.next.next != null) {
        middle = current.next;
        current = current.next.next;
    }
    

    Try mapping out what this does on a 10-element list. You should find it does something like this:

    0 1 2 3 4 5 6 7 8 9
    m m   m   m   m
    c   c   c   c   c
    

    As you can see, current stops when it points to the second to last element, but middle is only 1 element before it, not at the half. Because of this the mergesort only removes 2-3 elements per run, not dividing it in half, so it is a height of O(n), not O(logn), and takes O(n) to get the middle element, giving an O(n^2) time complexity, not O(nlogn). Switch to middle = middle.next; in order to get the true middle element and back to O(nlogn).


  • 0
    J

    First of all, in your mergeSort(ListNode start, ListNode end), the 2nd parameter "end" is completely redundant. The reason is that unlike array, you can literally cut LinkedList into half by setting the Middle.next=null.

    Secondly, I think your algorithm is still O(nlogn). It doesn't matter whether the time of finding the middle is O(1) or O(n) because merging two sub-lists already costs O(n). The recursion depth is logn, hence overall O(nlogn).

    My code doesn't use a 2nd parameter, but it's essentially the same as yours and it got accepted.


  • 0
    M

    Thanks for the double check. That got me to look back and find where the mistake actually was.


  • 0
    J

    Actually I didn't look at his code as carefully as you did. But in principle (that is if there were no implementation errors), it should be O(nlogn)


  • 0
    F

    I have implemented selection sort, which has time complexity O(NlogN) and couldn't get accepted. The long linked list gives TLE.

    ListNode *selectionSortList(ListNode *head)
    {
    ListNode *i=head, *j, *min;
    while (i)
    {
        min=i; j=i->next;
        while (j)
        {
            if (min->val > j->val)
                min = j;
            j=j->next;
        }
        if (min!=i)
        {
            int temp = i->val;
            i->val = min->val;
            min->val = temp;
        }
        i=i->next;
    }
     return head;
    }
    

    Eventually, I solved this problem using Hashtables in O(2N) time, O(N) space.


  • 0
    S

    I think your calculation about complexity was wrong. Even if it takes O(n) to find the middle point, the complexity will still be O(nlogn). In that case, there will be O(2n) for each recursion of Mergesort(), and there will be logN of them, therefore the complexity becomes O(n+n)*O(logN) = O(2NlogN) = O(NlogN). Same


  • 0
    M

    If you are talking about the part before the edit, I agree. I messed that up, as jaycui said. After the edit, however, is a different calculation. It takes O(n) to find the midpoint, but takes O(n) levels of recursion since it only removes one or two elements at a time. O(n) per level * O(n) levels is O(n^2)


Log in to reply
 

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