Java solution with strict O(1) auxiliary space complexity


  • 30
    Y

    First of all, allow me to explain the meaning of strict O(1) auxiliary space complexity.

    It means the maximum number of memory used by the program, except the memory taken by the input data, doesn't change with the input size.
    This indicates that, strictly speaking, any solution that involves recursion can never have a strict O(1) auxiliary space complexity. Because the maximum recursion level depends on the the input size and each recursion call consumes memory on stack, thus the maximum number of memory used depends on the input size.


    Secondly, allow me to explain my solution based on merge sort.

    Assume the length of list is n, which is unknown at the beginning.

      level log(n)         [ A0, A2, A3, ... , An-2, An-1 ]
      ...
      level 2        [ A0, A1, A2,  A3 ], [A4, A5, A6, A7] ,... , [ ..., An-2, An-1 ]
      level 1        [ A0, A1], [A2,  A3 ], [A4, A5], [A6, A7] ,... , [An-2, An-1]
      level 0        [ A0 ], [ A1] , [ A2 ],  [ A3 ],... , [ An-2 ], [ An-1 ]
    

    At each level, each group only contains at maximum 2^level elements. Merge-sort theses groups pair by pair. Then level ++. Stop until 2^level > n.
    Assume the original input is :

      level 0        5, 3, 6, 1, 4, 2, 7
    

    After level 0, we got the length of the list and the list become:

      level 1        3, 5,   1, 6,    2, 4,    7
    

    Now each group contains 2 elements. After level 1, the list become:

      level 2        1, 3, 5, 6,    2, 4, 7
    

    Now each group contains 2^2 = 4 elements. After level 2, the list become:

      level 3        1, 2, 3, 4, 5, 6, 7
    

    Now, 2^3 > 7, stop.

    Time complexity:
    In each level, each node is visited by at maximum twice. And there are log(n) level. Thus the time complexity is O(2n* log n ) => O( n* log n )

    Here is the code:

    public class Solution {
    private class MergeHelper {
            public ListNode newHead;
            public ListNode newTail;
    }
    public ListNode sortList(ListNode head) {
        if ( head == null || head.next == null) {
            return head;
        }
        
        ListNode dummyHeadOne = new ListNode(0);
        ListNode dummyHeadTwo = new ListNode(0);
        ListNode dummySortedHead = new ListNode(0);
        ListNode dummySortedLast = dummySortedHead;
        ListNode unvisitedNode = head;
        MergeHelper mergeRst = new MergeHelper();
        
        int listLength = 0;
        int level = 0;
        while ( unvisitedNode != null && unvisitedNode.next != null ) {
            unvisitedNode = addNode ( dummyHeadOne, unvisitedNode, 1<<level);
            unvisitedNode = addNode ( dummyHeadTwo, unvisitedNode, 1<<level);
            merge ( dummyHeadOne.next, dummyHeadTwo.next, mergeRst);
            dummySortedLast.next = mergeRst.newHead;
            dummySortedLast = mergeRst.newTail;
            listLength += 2;
        }
        if (unvisitedNode != null) {
            dummySortedLast.next = unvisitedNode;
            listLength ++;
        }
        level ++;
        
        while ( listLength > 1 << level) {
            dummySortedLast = dummySortedHead;
            unvisitedNode = dummySortedHead.next;
            while (unvisitedNode != null) {
                unvisitedNode = addNode ( dummyHeadOne, unvisitedNode, 1<<level);
                unvisitedNode = addNode ( dummyHeadTwo, unvisitedNode, 1<<level);
                merge ( dummyHeadOne.next, dummyHeadTwo.next, mergeRst);
                dummySortedLast.next = mergeRst.newHead;
                dummySortedLast = mergeRst.newTail;
            }
            level ++;
        }
        
        return dummySortedHead.next;
    }
    
    /* merge listOne and listTwo. 
    Save the sorted list head into rst.newHead
    Save the last node of the sorted list into rst.newTail
    */
    private void merge (ListNode listOne, ListNode listTwo, MergeHelper rst) {
        ListNode dummyHead = new ListNode (0);
        ListNode lastNode = dummyHead;
        while (listOne != null && listTwo != null) {
            if ( listOne.val < listTwo.val ) {
                lastNode.next = listOne;
                listOne = listOne.next;
            } else {
                lastNode.next = listTwo;
                listTwo = listTwo.next;
            }
            lastNode = lastNode.next;
        }
        
        while (listOne != null) {
            lastNode.next = listOne;
            listOne = listOne.next;
            lastNode = lastNode.next;
        }
        while ( listTwo != null ) {
            lastNode.next = listTwo;
            listTwo = listTwo.next;
            lastNode = lastNode.next;
        }
        rst.newHead = dummyHead.next;
        rst.newTail = lastNode;
    }
    
    /*
     add at max #"count" nodes into "head" from "source"
     return the new position of source after adding.
    */
    private ListNode addNode ( ListNode head, ListNode source, int count ) {
        while (count > 0 && source != null) {
            head.next = source;
            head = head.next;
            source = source.next;
            count --;
        }
        head.next = null;
        return source;
    }}
    

    Space complexity:
    There are no recursion calls in this solution. Thus the maximum number of function calls is constant.
    The number of dummy nodes is constant.
    Thus the auxiliary space complexity is O(1).


  • 0
    Y

    Nice solution and detailed explanation, thanks~


  • 0
    B

    so is this basically iterative version of merge sort?


  • 0
    T

    As you merge, you new a node. Does it use O(lgn) memory ?


  • 0
    N

    I believe the space complexity for his solution is still constant.

    He did new a node in the merge method. However, the scale of the object(new node) is in the method. Therefore, after the method return (finished), the object is died and the memory is recycled by the Java garbage collections.

    BTW, thanks yuanliay for sharing the nice solution with clear comments in the codes.


  • 0
    X

    Helpful explanation of space complexity and your solution.


Log in to reply
 

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