Python again, how to improve so that run time will be below 500ms?


  • 2
    O

    After lots of TLE, I modified the post from jianchao.li.fighter as below, but it still took about 1664ms.

    I saw lots of people were in the "<500ms group", how did you do that!?
    Could someone give me a hint? Thanks a lot!

    class Solution:
    # @param {ListNode} head
    # @return {ListNode}
    def insertionSortList(self, head):
    	newhead = ListNode(0)
    	newhead.next = head
    	pre, cur = newhead, head
    	while cur:
    		if cur.next and cur.next.val < cur.val:
    			while pre.next and pre.next.val < cur.next.val:
    				pre = pre.next
    			tmp = pre.next
    			pre.next = cur.next
    			cur.next = cur.next.next
    			pre.next.next = tmp
    			pre = newhead
    		else:
    			cur = cur.next
    	return newhead.next
    

  • 3

    I just submitted yours and it now gets accepted in about 430 ms. Could be the new-style classes LeetCode is using now, see this thread for a small discussion, including speed test results.

    Furthermore, doing

                val = cur.next.val
                while pre.next and pre.next.val < val:
    

    gets it down to about 345 ms. Doing

                val = cur.next.val
                while True:
                    next = pre.next
                    if not next or next.val >= val:
                        break
                    pre = next
    

    gets it down to about 310 ms.


  • 0
    O

    Thank you so much!!


  • 0
    M

    what is the meaning of cur.next = cur.next.next? thanks


  • 0
    O

    A-B-C will become A-C


  • 0
    M

    oh, I got it. Thanks a lot !!


  • 0
    S

    There's a test case that essentially checks if you're doing insertion sort in the classical sense, i.e. from right to left, rather than from left to right.

    That's a bit of a pain with a singly LinkedList (and I don't think it's possible if you want to maintain O(1) space complexity).

    Modifying your code to check if the target value is greater than or equal to the predecessor and to break if so should dramatically improve the performance.


Log in to reply
 

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