Find a specific pair in matrix

The problem, simply

You get an n by n grid of whole numbers, which can be negative. The grid is not sorted in any way.

Pick two cells. The first is at row a, column b. The second is at row c, column d, and it must be strictly lower and strictly further right: c > a and d > b. Find the biggest possible value of mat[c][d] - mat[a][b].

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every start cell with every end cell that is lower and further right, and keep the best difference.

1. For each start (a, b) that is not in the last row or column.
2. For each end (c, d) with c > a and d > b.
3. Keep the biggest mat[c][d] - mat[a][b].

class Solution {
    public int findMaxValue(int[][] mat) {
        int n = mat.length;
        int best = Integer.MIN_VALUE;
        for (int a = 0; a < n - 1; a++)
            for (int b = 0; b < n - 1; b++)            // every start cell
                for (int c = a + 1; c < n; c++)
                    for (int d = b + 1; d < n; d++)    // every end cell lower and further right
                        best = Math.max(best, mat[c][d] - mat[a][b]);
        return best;
    }
}

How long it takes: four loops of size up to n, O(n^4). Extra room: O(1).

Way 2: the clever way

For a start cell (i, j), the best end is the biggest number in the block of rows i+1 and down, columns j+1 and right. So build a table big where big[i][j] is the biggest number at (i, j) or anywhere below and to the right of it. Then the best end for start (i, j) is big[i+1][j+1].

The table is easy to fill from the bottom right corner, because each block is the cell itself plus the block below it plus the block to its right:

big[i][j] = max(mat[i][j], big[i+1][j], big[i][j+1])

1. Fill the last row from right to left, and the last column from bottom to top.
2. Go through the other cells from the bottom right toward the top left. For each one, first try it as a start: big[i+1][j+1] - mat[i][j]. Then fill big[i][j].

class Solution {
    public int findMaxValue(int[][] mat) {
        int n = mat.length;
        if (n < 2) return Integer.MIN_VALUE;         // no legal pair
        int[][] big = new int[n][n];                 // biggest at or below right of each cell

        big[n - 1][n - 1] = mat[n - 1][n - 1];
        for (int j = n - 2; j >= 0; j--) big[n - 1][j] = Math.max(mat[n - 1][j], big[n - 1][j + 1]);   // last row
        for (int i = n - 2; i >= 0; i--) big[i][n - 1] = Math.max(mat[i][n - 1], big[i + 1][n - 1]);   // last column

        int best = Integer.MIN_VALUE;
        for (int i = n - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                best = Math.max(best, big[i + 1][j + 1] - mat[i][j]);   // this cell as the start
                big[i][j] = Math.max(mat[i][j], Math.max(big[i + 1][j], big[i][j + 1]));
            }
        }
        return best;
    }
}

How long it takes: every cell is filled once with a few comparisons, O(n^2). Extra room: the table, O(n^2).

Watch out for

• Starting best at 0. If every legal pair goes down, the true answer is negative.
• Filling the table in the wrong order. big[i+1][j] and big[i][j+1] must already be ready, so go from the bottom right toward the top left.
• Sorting assumptions. Some write ups say the grid is sorted. It is not, and the method does not need it. If it were sorted, the answer would be the bottom right minus the top left.
• Very large numbers: the difference of two int values can overflow. Use long if values can be near the int limits.

What interviewers ask next

• Can you use less room? Yes. When you fill row i, you only read row i + 1. Keep one array for the row below and one for the current row, so O(n) room.
• Can you also return the two cells? Store, next to each big value, where that biggest number lives. When best improves, record (i, j) and that position.
• The one row version: the biggest a[j] - a[i] with j > i. Walk from the right keeping the biggest number seen. That is the same idea in one direction, like the best time to buy and sell a stock.
• What if the end may share a row or a column with the start (c >= a, d >= b, but not the same cell)? Use max(big[i+1][j], big[i][j+1]) as the best partner. Those two blocks cover everything except the cell itself.
• A rectangle version: the biggest sum of any sub grid. That is a different problem (Kadane's idea on pairs of rows), but interviewers like to ask it next.

Remember this

Grown-up words: the numbers written on the map form a suffix maximum table (a small 2D dynamic programming table), filling from the corner is the order that makes each cell depend only on finished cells, and trying every start with one lookup is what turns O(n^4) into O(n^2).