O(nk) solution. Help speed up this method without Heap or recursion.


  • 0
    D

    Hi,
    This is an accepted solution. How can I speed up this solution?. The only part where i can speed up is where I am doing repeated look up ok (k-1) old elements to find min.
    How can I improve without Priority queues?

    The only thing I come up with is insert each element into PQ as I read K and then continuously call getMin() and Insert of new element.

    Time Complexity:

    for each n: find min(k) (n = total elements)
    = O(nk)

    public class Solution {
        public ListNode MergeKLists(ListNode[] lists) {
            if(lists.Length==0) return null;
            if(lists.Length==1) return lists[0];
    
            ListNode head = new ListNode(0);
            ListNode current = head;
    
            int k = lists.Length;
            int completed = 0;
            ListNode[] ptr = new ListNode[k];
            int counter = 0;
            foreach(ListNode headNode in lists){
                ptr[counter++] = headNode;
                if(headNode==null) completed++;
            }
            while(k-completed>0){
                int minPtr = -1;
                int min = Int32.MaxValue;
                
                for(int i=0 ; i<k ; i++){
                    if( ptr[i]==null ) continue;
                    else if( ptr[i].val<min ){
                        min = ptr[i].val;
                        minPtr = i;
                    }
                }
               if(minPtr!=-1){
                   current.next = ptr[minPtr];
                   current = current.next;
                   ptr[minPtr] = ptr[minPtr].next;
                    if(ptr[minPtr]==null) completed++;
               }
            }
            return head.next;
        }
    }
    

Log in to reply
 

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