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

  • 0

    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++;
                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;
                   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.