Print elements in sorted order using row-column wise sorted matrix

The problem, simply

You get a grid with m rows and n columns. Every row is sorted from left to right, and every column is sorted from top to bottom.

Print all m * n numbers from smallest to biggest.

Being sorted both ways is not enough to read the grid row by row. In the picture below, row 2 starts with 27, which is smaller than 30 at the end of row 0.

A story to remember it

Picture it

Examples

Way 1: the simple way

Pour every number into one long line and sort it.

1. Copy all numbers into an array.
2. Sort the array.
3. Print it.

import java.util.*;

class Solution {
    public int[] sortedOrder(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[] all = new int[m * n];
        int k = 0;
        for (int[] row : matrix)
            for (int value : row) all[k++] = value;
        Arrays.sort(all);               // sorting ignores that rows were already sorted
        return all;
    }
}

How long it takes: sorting m * n numbers, O(m*n*log(m*n)). Extra room: the copy, O(m*n).

Way 2: the clever way

Each row is a sorted line. Merging sorted lines is what the lunch lady does. Keep the front number of every row in a min heap, a pile where the smallest number is always on top and can be taken out quickly.

1. Put (matrix[r][0], r, 0) into the heap for every row r. We store the row and column too, so we know who steps up next.
2. Pop the smallest. Print it.
3. If its row has a next number, push that number into the heap.
4. Repeat until the heap is empty.

The heap never holds more than m numbers, one per row.

import java.util.*;

class Solution {
    public int[] sortedOrder(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[] result = new int[m * n];
        int k = 0;

        // each entry is {value, row, col}; smallest value on top
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        for (int r = 0; r < m; r++) heap.offer(new int[]{matrix[r][0], r, 0});   // front of every line

        while (!heap.isEmpty()) {
            int[] top = heap.poll();                 // the smallest front anywhere
            result[k++] = top[0];
            int r = top[1], c = top[2];
            if (c + 1 < n) heap.offer(new int[]{matrix[r][c + 1], r, c + 1});   // next kid steps up
        }
        return result;
    }
}

How long it takes: every number goes into the heap once and out once. Each of those costs O(log m) because the heap holds at most m numbers. Total O(m*n*log(m)). Extra room: the heap, O(m), besides the answer.

If m is bigger than n, put the columns in the heap instead of the rows (columns are sorted too). Then it is O(m*n*log(min(m, n))).

Watch out for

• Storing only the value in the heap. Then you do not know which row the number came from, so you do not know who steps up next.
• Pushing the number below (from the column) as well as the number to the right. Then the same cell can enter the heap twice. If you go that way, keep a visited set.
• An empty grid or empty rows. Return an empty array before reading matrix[0].

What interviewers ask next

• Only the kth smallest? Stop after k pops. That is O(k log m). The Kth smallest problem also has a binary search on values that needs only O(1) room.
• Can you use both sort directions? Start the heap with only the top left cell. When you pop (r, c), push (r + 1, c) and (r, c + 1) if not visited yet. Correct, but the heap can grow to about m + n numbers instead of m.
• Merge k sorted linked lists. Same heap of fronts, with list nodes instead of grid cells.
• Can you do it with no heap? Merge rows two at a time like merge sort: merge row 0 with row 1, row 2 with row 3, and so on. That is also O(m*n*log(m)) time but needs O(m*n) room for the merged lines.
• Why is the top left always the smallest and the bottom right always the biggest? Every other cell can be reached from the top left by moving right and down, and each move only makes the number bigger. A grid like this is called a Young tableau.

Remember this

Grown-up words: the lunch lines are sorted rows, the pile with the youngest on top is a min heap or priority queue, and serving across all lines is a k way merge.