title: Merge k sorted arrays of size n in O(nk) time complexity
body: <p>Recently in an interview I was asked this question: </p>
  
  <blockquote>
    <p><em>Merge k sorted arrays each with n elements into a single array of size n</em>k in minimum time complexity.*</p>
  </blockquote>
  
  <p>I gave a solution using a minheap of size k to find the minimum of the top elements of the k lists.</p>
  
  <p>This way the time complexity would come down to - O(nklogk).</p>
  
  <p>But he wasn't convinced. He wanted a solution with time complexity of O(nk).</p>
  
  <p>I have searched on internet, but I couldn't find a solution.</p>