174. Merge K Sorted Arrays

Given k sorted arrays (each given as its length followed by its sorted values), merge all of them into a single fully sorted array and print it.

Input: The first line contains an integer k, the number of arrays. Each array is given as a line with its length, followed by a line of that many space-separated sorted integers. Output: Print the single fully merged, sorted array, space-separated.

1 <= k <= 100, 1 <= each array's length <= 1000

This exact 'seed a heap with one candidate per source, pop-and-replace' technique reappears in 'Smallest Range Covering Elements From K Lists' and 'Kth Smallest Element in a Row-Wise and Column-Wise Sorted Matrix' - recognizing it as a reusable k-way-merge pattern is valuable.

Given several already-sorted arrays, combine them all into one single, fully sorted array. Brute force: Concatenate all k arrays into one big list and run a general-purpose sort on the whole thing - this costs O(N log N) where N is the total element count across all arrays, ignoring that each individual array is ALREADY sorted. Optimised: A min-heap holding just ONE candidate per array (its current front) lets you always find the next-smallest value across ALL arrays combined in O(log k) time - since each array is already sorted internally, you never need to reconsider elements already passed, giving an overall merge cost proportional to the total element count times log k, rather than log N.

Merge the first two sorted arrays together using the standard linear two-pointer merge, then merge that result with the third array, then the fourth, and so on until all k arrays have been folded together. This is correct because merging two sorted sequences always produces a sorted sequence, and repeating this against every remaining array eventually combines all values in order; it's an improvement over full re-sorting since it exploits the arrays' existing order, though the accumulated result gets rescanned against each new array, so the cost scales with the number of arrays. Time: O(N * k) Space: O(N)

Copy every element from all k arrays into a single combined array, then sort that combined array from scratch. This is correct because sorting any collection of numbers, regardless of their original grouping, produces the fully merged sorted order, but it completely disregards the fact that each of the k input arrays was already individually sorted, redoing comparison work that didn't need to happen. Time: O(N log N) Space: O(N)

Push the first element of each of the k arrays into a min-heap along with which array and index it came from, then repeatedly pop the overall smallest element, append it to the output, and push the next element from that same array (if any remain) into the heap. This is correct because the heap always surfaces the globally smallest not-yet-output candidate across all k arrays, and since each of the N total elements only costs a single O(log k) heap operation instead of being compared against an ever-growing merged array, it scales far better as the number of arrays grows. Time: O(N log k) Space: O(k)

1. Seed a min-heap with the FIRST element of every array (along with which array and index it came from). 2. Repeatedly pop the heap's minimum, output it, and push that same array's NEXT element (if one exists) back into the heap. 3. Continue until every array has been fully exhausted.

Time: O(N log k), where N is the total number of elements across all k arrays - each of the N elements triggers one O(log k) heap operation. Space: O(k), for the heap holding at most one candidate per array at any time.

k = 1 (the output equals that one array unchanged), arrays of very different lengths, and k up to 100 with each array up to 1000 elements for performance.

Be ready to connect this directly to 'merge two sorted arrays' (the two-pointer technique) - this is its natural k-way generalization, replacing two simple pointers with a heap to efficiently track the minimum among many candidates at once.