Print elements in sorted order (row- and column-sorted matrix)
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]
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).