I believe my code is under O(n) space not O(1), but I still got passed. What is my space comlexity anyway?


  • 0
    S
    class Solution {
    public:
    ListNode* Merge(ListNode* list1, ListNode* list2){//list1 2; list2 4
        ListNode* result = new ListNode(0);
        ListNode* travel = result;
        while(list1 || list2){
            if(!list1){
                travel->val = list2->val;
                list2 = list2->next;
                if(list1 || list2){
                    travel->next = new ListNode(0);
                    travel = travel->next;
                }
            }
            else if(!list2){
                travel->val = list1->val;
                list1 = list1->next;
                if(list1 || list2){
                    travel->next = new ListNode(0);
                    travel = travel->next;
                }
            }
            else{
                if(list1->val <= list2->val){
                    travel->next = new ListNode(0);
                    travel->val = list1->val;
                    list1 = list1->next;
                    travel = travel->next;
                }
                else{
                    travel->next = new ListNode(0);
                    travel->val = list2->val;
                    list2 = list2->next;
                    travel = travel->next;
                }
            }
        }
        
        return result;
    }
    
    ListNode* MergeSort(ListNode *head, ListNode* end){
        if(head == end){
            ListNode* result = new ListNode(head->val);
            return result;
        }
        else{
            ListNode* slow = head;
            ListNode* fast = head;
            while(fast != end && fast->next != end && fast->next->next != end){
                fast = fast->next;
                fast = fast->next;
                slow = slow->next;
            }
            ListNode* list1 = MergeSort(head, slow);//2,3
            ListNode* list2 = MergeSort(slow->next, end);//4
            return Merge(list1, list2);
        }
    }
    
    ListNode *sortList(ListNode *head) {
        ListNode* travel1 = head;
        if(!travel1) return NULL;
        ListNode* travel2 = travel1->next;
        if(!travel2) return travel1;
        while(travel2){
            travel2 = travel2->next;
            travel1 = travel1->next;
        }
        ListNode* end = travel1;
        return MergeSort(head, end);
    }
    
    };
    

    When I was implementing the Merge, I used a new node in heap memory in O(n) space, but I never got warned. Does it mean that this implementation is still under O(1) space constrain? If not, will there be anyway for mergesort to help me keep my code under this constrain?

    Best,
    Siyi


  • 2
    M

    Leetcode does not track memory very closely. Unlike time complexity, memory limits only fail you when you use more memory than is allocated, which is very rarely tied to the requirements of the challenge. Therefore, when the problem asks for O(1) space, you need to check that yourself, not rely on leetcode to detect that for you.

    As a matter of fact, your current algorithm has a space complexity of, I believe, O(nlogn), since every step of the merge generates a new node. There is a way to do it in O(1), but the top-down recursive method does not work, since at the very least, the stack will take O(logn) space while splitting the nodes. Try looking at bottom-up merge sort.


  • 0
    S

    Thanks Mike! I have never heard of the bottom-up merge before! And I think the O(1) space complexity method will be using this bottom-up merge insert node into the linked list so that we do not need the buffer array in Wiki anymore? That is really alot of work!

    And what if I have some general questions about technical interview(skills and the way of explain your thought), do you happen to know what area is proper for me to post it?


  • 0
    M

    Leetcode is more for the technical questions than for explaining thoughts. If you want to practice that here, I would suggest you read the questions and try to answer them. If you don't explain well, people will also answer, or will ask questions about your explanations.

    I suggest checking with this site:
    http://programmers.stackexchange.com/questions/80065/preparing-for-interviews


Log in to reply
 

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