v9.1.1
Menu

Merge K Sorted Lists

hardFREEHeaps & Priority QueuesDSA for AI Engineers

Given k sorted arrays, merge them into one sorted array.

Implement merge_k_sorted(lists), where lists is a list of k lists of integers, each sorted in ascending order (some may be empty, and lists itself may be empty). Return a single list containing every element of every input list, sorted in ascending order, with duplicates kept. The tests print the returned list space-separated.

In the example below, each input line is one of the sorted arrays (comma-separated), and the output is the merged array, space-separated.

Example

Input
1,4,5
1,3,4
2,6
Output
1 1 2 3 4 4 5 6
Reasoning
  • The input lists holds k=3k = 3 sorted arrays: [1,4,5][1, 4, 5], [1,3,4][1, 3, 4] and [2,6][2, 6], with 3+3+2=83 + 3 + 2 = 8 numbers in total.
  • The output must contain every one of those 8 numbers exactly once, arranged so that each value is no larger than the next: 1≤1≤2≤3≤4≤4≤5≤61 \le 1 \le 2 \le 3 \le 4 \le 4 \le 5 \le 6.
  • Why does 11 come first? The overall minimum is min⁡(1,1,2)=1\min(1, 1, 2) = 1: because each array is ascending, its smallest value is its first one, so the global minimum must be one of the three front values.
  • Duplicates are kept, not removed: the two 11s come from the first and second arrays, and the two 44s also come one from each of those arrays.
  • Notice that the arrays may differ in length: [2,6][2, 6] is shorter, yet its 66 is the largest value overall and lands last.
  • Printed space-separated, the merged result is 1 1 2 3 4 4 5 6.

Constraints

  • 0 <= k <= 10^4
  • 0 <= total elements <= 10^4
  • Arrays are sorted in ascending order

More from DSA for AI Engineers

solution.py

Test results

Sign in to run your code against the test cases.