Given an n x n integer matrix mat, we want to find the maximum difference mat[c][d] - mat[a][b] across all coordinate pairs (a, b) and (c, d) that satisfy the strict dominance condition c > a and d > b. In geometric terms, the second element mat[c][d] must lie strictly below and strictly to the right of the first element mat[a][b].

Problem Statement and Walkthrough Example

A naive brute-force search checks every valid pair of coordinates (a, b) and (c, d) in O(n^4) time, which times out when n = 1000 (where n^2 = 10^6 cells). By reformulating the query with 2D dynamic programming, we reduce the runtime to optimal O(n^2) time.

Example Matrix

Input: mat = [
  [  1,  2, -1, -4, -20 ],
  [ -8, -3,  4,  2,   1 ],
  [  3,  8,  6,  1,   3 ],
  [ -4, -1,  1,  7,  -6 ],
  [  0, -4, 10, -5,   1 ]
]
Output: 18
Explanation:
Selecting (a, b) = (1, 0) where mat[1][0] = -8 and (c, d) = (4, 2) where mat[4][2] = 10
satisfies c > a (4 > 1) and d > b (2 > 0), yielding 10 - (-8) = 18.

Constraints

• 2 <= n <= 1000
• -1000 <= mat[i][j] <= 1000

2D Suffix Maximum Dynamic Programming Formulation

Suppose we fix the top-left coordinate (i, j). To maximize mat[c][d] - mat[i][j] over all c >= i + 1 and d >= j + 1, we simply need the largest value inside the bottom-right submatrix starting at (i + 1, j + 1) and extending to (n - 1, n - 1).

Define suffixMax[i][j] as the maximum element in the submatrix mat[i..n-1][j..n-1]. Moving from the bottom-right corner (n - 1, n - 1) toward the top-left corner (0, 0), we can compute suffixMax[i][j] in O(1) time per cell:

// Base cases on the last row and last column:
suffixMax[n - 1][n - 1] = mat[n - 1][n - 1];
suffixMax[n - 1][j]     = max(mat[n - 1][j], suffixMax[n - 1][j + 1]);
suffixMax[i][n - 1]     = max(mat[i][n - 1], suffixMax[i + 1][n - 1]);

// Interior transition for 0 <= i < n - 1 and 0 <= j < n - 1:
candidateDiff           = suffixMax[i + 1][j + 1] - mat[i][j];
suffixMax[i][j]         = max({ mat[i][j], suffixMax[i + 1][j], suffixMax[i][j + 1] });

C++20 Implementation (O(n^2) Time)

Below is the clean C++20 implementation using reverse matrix traversal from (n - 1, n - 1) to (0, 0):

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

int findMaxPairDifference(const std::vector<std::vector<int>>& mat) {
    const int n = static_cast<int>(mat.size());
    std::vector<std::vector<int>> suffixMax(n, std::vector<int>(n, 0));
    int maxDiff = INT_MIN;

    // 1. Anchor bottom-right corner
    suffixMax[n - 1][n - 1] = mat[n - 1][n - 1];

    // 2. Precompute suffix maximums along the bottom row
    for (int j = n - 2; j >= 0; --j) {
        suffixMax[n - 1][j] = std::max(mat[n - 1][j], suffixMax[n - 1][j + 1]);
    }

    // 3. Precompute suffix maximums along the rightmost column
    for (int i = n - 2; i >= 0; --i) {
        suffixMax[i][n - 1] = std::max(mat[i][n - 1], suffixMax[i + 1][n - 1]);
    }

    // 4. Sweep interior cells from bottom-right to top-left
    for (int i = n - 2; i >= 0; --i) {
        for (int j = n - 2; j >= 0; --j) {
            maxDiff = std::max(maxDiff, suffixMax[i + 1][j + 1] - mat[i][j]);
            suffixMax[i][j] = std::max({
                mat[i][j],
                suffixMax[i + 1][j],
                suffixMax[i][j + 1]
            });
        }
    }

    return maxDiff;
}

int main() {
    std::vector<std::vector<int>> mat = {
        {  1,  2, -1, -4, -20 },
        { -8, -3,  4,  2,   1 },
        {  3,  8,  6,  1,   3 },
        { -4, -1,  1,  7,  -6 },
        {  0, -4, 10, -5,   1 }
    };
    std::cout << "Maximum Difference: " << findMaxPairDifference(mat) << "\n"; // 18
    return 0;
}

Space-Optimized TypeScript Implementation (O(n) Auxiliary Space)

Notice that computing row i of suffixMax only ever reads from row i + 1 (specifically suffixMax[i + 1][j + 1] and suffixMax[i + 1][j]) and the cell immediately to the right (suffixMax[i][j + 1]). We can therefore compress the 2D table into a single 1D rolling row of length n, cutting auxiliary memory from O(n^2) to O(n):

export function maxMatrixPairDifference(mat: ReadonlyArray<ReadonlyArray<number>>): number {
  const n = mat.length;
  if (n < 2) {
    throw new Error('Matrix dimension n must be at least 2.');
  }

  // nextRow[j] holds suffixMax[i + 1][j]
  const nextRow = new Int32Array(n);
  nextRow[n - 1] = mat[n - 1][n - 1];
  for (let j = n - 2; j >= 0; j--) {
    nextRow[j] = Math.max(mat[n - 1][j], nextRow[j + 1]);
  }

  let maxDiff = -Infinity;

  for (let i = n - 2; i >= 0; i--) {
    let prevDiagSuffixMax = nextRow[n - 1]; // suffixMax[i + 1][j + 1]
    nextRow[n - 1] = Math.max(mat[i][n - 1], nextRow[n - 1]);

    for (let j = n - 2; j >= 0; j--) {
      const belowSuffixMax = nextRow[j]; // suffixMax[i + 1][j] before overwrite
      maxDiff = Math.max(maxDiff, prevDiagSuffixMax - mat[i][j]);

      nextRow[j] = Math.max(mat[i][j], belowSuffixMax, nextRow[j + 1]);
      prevDiagSuffixMax = belowSuffixMax;
    }
  }

  return maxDiff;
}

Time and Space Complexity Comparison