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

• 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];

int k = lists.Length;
int completed = 0;
ListNode[] ptr = new ListNode[k];
int counter = 0;
}
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++;
}
}