Print elements in sorted order (row- and column-sorted matrix)

Medium

Problem

Every row and every column of an n × n matrix is sorted. Print all its elements in sorted order.

Example 1

Input:  [[10,20,30,40], [15,25,35,45], [27,29,37,48], [32,33,39,50]]
Output: 10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50

Also asked as: Print elements in sorted order using row-column wise sorted matrix

Test cases

Case 1

Input:    [[10,20,30,40],[15,25,35,45],[27,29,37,48],[32,33,39,50]]
Expected: [10,15,20,25,27,29,30,32,33,35,37,39,40,45,48,50]

Case 2

Input:    [[1,3],[2,4]]
Expected: [1,2,3,4]

Case 3

Input:    [[1,1],[1,2]]
Expected: [1,1,1,2]

Case 4

Input:    [[7]]
Expected: [7]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Min-heap of row frontiers (merge k sorted lists)

Time O(R·C · log R)Space O(R)

Each row is sorted; push the first cell of every row into a min-heap, pop the smallest, and push the next cell from that row.

function sortedOrder(m) {
const heap = m.map((row, r) => [row[0], r, 0]);
heap.sort((a, b) => a[0] - b[0]);
const out = [];
while (heap.length) {
const [val, r, c] = heap.shift();
out.push(val);
if (c + 1 < m[r].length) {
const next = [m[r][c + 1], r, c + 1];
let i = heap.findIndex((x) => x[0] > next[0]);
i === -1 ? heap.push(next) : heap.splice(i, 0, next);
}
}
return out;
}

Shown with a sorted array for brevity; a real binary min-heap makes each push/pop O(log R).