Is the complexity O(kn)?


  • 1
    Y

    Here is my solution. Is it O(kn)? Do you guys have better solutions?

     /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        public ListNode mergeKLists(ArrayList<ListNode> lists) {
            // Note: The Solution object is instantiated only once and is reused by each test case.
            if (lists == null) return null;
            if (lists.isEmpty()) return null;
    		ListNode head = new ListNode(0);
    		ListNode tail = head;
            while (lists.size() > 0) {
    	        int toRemove = -1;
    	        int emptyCount = 0;
    	        for (int i = 0; i < lists.size(); i++) {
    	        	if (lists.get(i) != null) {
    	        		if (toRemove == -1) toRemove = i;
    		        	else {
    		        		if (lists.get(i).val < lists.get(toRemove).val) {
    		        			toRemove = i;
    		        		}
    		        	}
    	        	} else {
    	        		emptyCount++;
    	        	}
    	        }
    	        if (emptyCount == lists.size()) break;
    	        ListNode toDelete = lists.remove(toRemove);
    	        tail.next = toDelete;
    	        tail = tail.next;
    	        lists.add(toDelete.next);
            }
            tail.next = null;
            return head.next;
        }
    }

  • 0

    Hi Ynisgol, welcome! Could you spend some time explaining your approach, so that the community understand which part of your solution that could be improve?


  • 0
    Z

    i know it's O(n) time complexity for k=2, so O(kn) should be correct. Space is O(1) if u r merging to one of the original lists.

    You can surely do O(nlogk) if you do something like merge sort. Eg. for k=4, merge l2 to l1, l4 to l3, then l3 to l1.


  • 0
    S

    Thanks zchen! Seems you provide an answer for this question, not just a comment. Could you please paste your content and post it as answer?


  • 4
    Z

    My idea is based on merge 2 sorted list. If we merge every adjacent 2 lists per iteration, we needs log2(k) iterations, where merge 2 sorted list costs O(n) per iteration. Thus the run time is O(log(k)n).

    public class Solution {
        public ListNode mergeKLists(ArrayList<ListNode> lists) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            if(lists.isEmpty()) return null;
            if(lists.size() == 1) return lists.get(0);
            int k = lists.size();
            int log = (int)(Math.log(k)/Math.log(2));
            log = log < Math.log(k)/Math.log(2)? log+1:log; // take ceiling
            for(int i = 1; i <= log; i++){
                for(int j = 0; j < lists.size(); j=j+(int)Math.pow(2,i)){
                    int offset = j+(int)Math.pow(2,i-1);
                    lists.set(j, mergeTwoLists(lists.get(j), (offset >= lists.size()? null : lists.get(offset))));
                }
            }
            return lists.get(0);
        }
        
        
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            if(l1 == null) return l2;
            if(l2 == null) return l1;
            ListNode head = l1.val > l2.val? l2:l1;
            if(head.equals(l2)){
                l2 = l1;
                l1 = head;
            }
            while(l1.next != null && l2 != null){
                if(l1.next.val > l2.val){
                    ListNode tmp = l1.next;
                    l1.next = l2;
                    l2 = l2.next;
                    l1 = l1.next;
                    l1.next = tmp;
                }
                else
                    l1 = l1.next;
            }
            if(l2 != null){
                l1.next = l2;
            }
            return head;
        }
    }

  • 3
    U

    Use a heap, then you can get a better time complexity. O(n * log(k))


  • 1
    J

    However, in this case, we need O(k) extra memory.


  • 0
    X

    shouldn't this be O(log(k) k n)? since the size of your list grows as you do more iterations, you can't simply assume the time for merging is O(n) for every iteration. in fact, at each iteration you do same amount of work of O(kn). correct me if i'm wrong


  • 0
    X

    can you explain why it is O(n * log(k)) using a heap?
    if you maintain a heap of size k, then insert every element in k lists, then you'll have to insert O(kn) elements in total, and each insertion takes O(logk), each remove takes O(1), so the total runtime will be O(kn logk), did I miss something here?


  • 0
    U

    In this Problem, n is the total number of elements, so there are n elements to be inserted, but not n elements.


  • 0
    G

    I agree with xnliu, this should be O(k log(k) n), because each time the length of the lists doubles.


  • 0
    N

    If n is the total number of elements in all lists, then each iteration you go through all the elements just once. The length of each list doubles, but the number of lists in the vector halves, so the total length of all lists remains at n. So O(log(k)n).


  • 0
    G

    If n is the total number of elements in all lists, then it's O(log(k)n), but if n is the number of elements in one list, then it's O(klog(k)n).


  • 0
    Y

    This line
    ListNode toDelete = lists.remove(toRemove);

    will remove all Linklist from arrayList, It looks not right for me. Should we only remove the head of linkedList, and move to next one? But I test the code above in OJ, it is accptyed. Could someone add more explaination?


  • 0
    S

    Below is my C++ implementation of zchen's idea, running in O(Nlogk) or O(nklogk), where k is the number of lists, n the average number of nodes in each list, and N = nk. It may be slight faster than zchen's since it does not require the explicit computation of logK and pow(2,i). The idea is to maintain two indices a and b of the list array (a, b < k). In every iteration, merge lists[a] and lists[b], then move a and b to the next locations. If either a or b reaches the end of the list, then rewind them to the beginning of the array, and double the distance between them. If the distance between them is already greater than n, then quit.

    ListNode *mergeTwoLists(ListNode* a, ListNode* b)
    {
        if (a == NULL) return b;
        if (b == NULL) return a;
        
        ListNode* head, *cur, *next1, *next2;
        if (a->val <= b->val) {cur = a; next1 = cur->next; next2 = b;}
        else {cur = b; next1 = cur->next; next2 = a;}
        
        head = cur;
        while (next1 && next2)
        {
            if (next1->val <= next2->val) {cur->next = next1; cur = next1; next1 = next1->next;}
            else {cur->next = next2; cur = next2; next2 = next2->next;}
        }
        if (next1) cur->next = next1;
        else cur->next = next2;
        return head;
    
    }
    
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        int n = lists.size();
        if (n == 0) return NULL;
        int stride = 1;
        int a = 0;
        int b = stride;
        while (stride < n)
        {
            lists[a] = mergeTwoLists(lists[a], lists[b]);
            a = b + stride; // Proceed to the next merging positions
            b = a + stride;
            // If the next two merging positions exceed the limit of vector
            // then go back to the beginning of vector and double the stride
    
            if (a >= n || b >= n) {stride <<= 1; a = 0; b = stride;}
        }
        return lists[0];
    }

  • 0
    P

    This is my approach using a Heap (PriorityQueue in Java).
    Let's say the longest ListNode has n elements. You would need to add at least k times n elements to the heap. Therefor, the time to add the last element would be O(Log(kn)). Thus, the time to add all elements is bound by O(k*Log(kn)). The analysis for the rest of the algorithm is analogous.

    Cheers.

    import java.util.*;
    
    public class Solution {
        public ListNode mergeKLists(List<ListNode> lists) {
            PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
    		
    		for(ListNode x : lists) {
    		    while(x!=null) {
    		        heap.add(x.val);
    		        x = x.next;
    		    }
    		}
    		
    		if(heap.isEmpty() || lists.isEmpty()) return null;
    		
    		ListNode result = new ListNode(heap.remove());
    		ListNode first = result;
    		int counter = heap.size();
    		for(int i=0; i<counter; i++) {
    			result.next = new ListNode(heap.remove());
    			result = result.next;
    		}
    		return first;
    	}
    }

  • 0
    E

    for each node insert into the heap, it took(log1+log2+log3....+logn) = O(nlogn), and for iterate the heap, it took n, so complexity would be O(nlogn), and this way took lots of extra space.


  • 0
    H
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 0
    N

    Basically what it does is removing smallest node every time and put it back to the newly constructed linkedlist. After the removing, this line,
    lists.add(toDelete.next);
    put the linkedlist back to the list after the smallest node of that linked list is remove.


Log in to reply
 

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