40. Print Elements in Sorted Order Using a Row-and-Column-Wise Sorted Matrix

Given an r x c matrix, print all its elements in ascending sorted order, space-separated on one line.

Input: The first line contains r and c, the matrix dimensions. The next r lines each contain c space-separated integers. Output: Print all matrix elements in ascending sorted order, space-separated on one line.

1 <= r, c <= 500

Row-and-column sortedness doesn't automatically mean the flattened array (read row by row) is sorted - it only guarantees local order within each row/column, which is precisely why a full sort (or the more clever heap-merge) is still needed.

Given a grid where every row and every column is individually sorted, print all its values in fully sorted order. Brute force: Flattening and sorting directly is itself already a perfectly valid, simple, and correct approach here - it's not really a 'worse' method, just a less specialized one. Optimised: A more advanced approach uses a min-heap seeded with each row's first element (the same 'merge k sorted lists' technique used in 'Kth Smallest Element in a Row-Wise and Column-Wise Sorted Matrix') to produce the sorted output without a full flatten-and-sort - useful when the grid is too large to comfortably sort as one big flat list, but for typical constraints here a plain sort is entirely acceptable and simpler to implement correctly.

Push the first element of every row into a min-heap, each tagged with its row and column. Repeatedly pop the smallest element, output it, and if that row has more elements, push the next one from that row into the heap. This performs the identical k-way merge as the linear-scan version, but finding and removing the minimum among the r active candidates now costs O(log r) via the heap instead of O(r) via linear scan, which is significantly faster when there are many rows. Time: O(rc log r) Space: O(r)

Maintain a pointer into each of the r rows (all starting at column 0). Repeatedly scan across all r current pointer positions to find the smallest value among them, output it, and advance that row's pointer, continuing until all rows are exhausted. This uses the fact that each row is already sorted to perform a k-way merge instead of a general sort, but finding the minimum among r candidates by linear scan at every one of the rc output steps costs extra work proportional to the number of rows. Time: O(r^2 * c) Space: O(rc)

Copy all r * c elements of the matrix into a single flat array, then sort that array with a general-purpose comparison sort and print the result. This produces the correct sorted output, but it completely ignores the fact that each row and each column is already individually sorted, so it does more comparison work than necessary. Time: O(rc log(rc)) Space: O(rc)

1. The simplest correct approach: collect every element from the grid into one flat list. 2. Sort that flat list. 3. Print it, space-separated.

Time: O(r*c log(r*c)) for the flatten-and-sort approach - dominated by the sort. Space: O(r*c), for the flattened list before and after sorting.

r = 1 or c = 1 (a single row or column); duplicate values across the matrix; and r = c = 500 (largest, confirming the sort/merge approach scales).

Be ready to mention the min-heap 'merge k sorted rows' alternative as a more specialized approach, even though a plain sort is fully acceptable here - showing you know BOTH options, and when each is appropriate, is what separates a good answer from a great one.