Find a specific pair in matrix

Problem Statement

Given an n x n matrix where every row and column is sorted in increasing order, find the maximum value of mat[c][d] - mat[a][b] such that c > a and d > b.

Example:

• Input: matrix = [[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: Maximum value is mat[4][2] - mat[1][0] = 10 - (-8) = 18

Approach 1: Brute Force

Intuition

Check all valid pairs where (c > a) and (d > b), and find the maximum difference.

Algorithm

1. For each cell (a, b), consider it as the "from" position
2. For each cell (c, d) where c > a and d > b, consider it as the "to" position
3. Calculate mat[c][d] - mat[a][b] and track maximum

public class Solution {
    public int findMaxValueBrute(int[][] mat) {
        int n = mat.length;
        int maxVal = Integer.MIN_VALUE;
        
        // For each starting cell (a, b)
        for (int a = 0; a < n - 1; a++) {
            for (int b = 0; b < n - 1; b++) {
                // For each ending cell (c, d) where c > a and d > b
                for (int c = a + 1; c < n; c++) {
                    for (int d = b + 1; d < n; d++) {
                        int diff = mat[c][d] - mat[a][b];
                        maxVal = Math.max(maxVal, diff);
                    }
                }
            }
        }
        
        return maxVal;
    }
}

Complexity Analysis

• Time Complexity: O(n^4) - Four nested loops
• Space Complexity: O(1) - Only using constant extra space

Approach 2: Precompute Maximum (Optimal)

Intuition

To maximize mat[c][d] - mat[a][b], for each cell (a, b), we need the maximum value in the submatrix to its bottom-right. We can precompute this maximum for all cells.

Let maxVal[i][j] = maximum value in submatrix from (i, j) to (n-1, n-1).

Then answer = max(maxVal[i+1][j+1] - mat[i][j]) for all valid (i, j).

Algorithm

1. Build maxVal matrix from bottom-right to top-left
2. For each cell (i, j), calculate maxVal[i+1][j+1] - mat[i][j]
3. Track the maximum difference

public class Solution {
    public int findMaxValue(int[][] mat) {
        int n = mat.length;
        if (n < 2) return Integer.MIN_VALUE;
        
        // maxVal[i][j] = max value in submatrix from (i,j) to (n-1, n-1)
        int[][] maxVal = new int[n][n];
        
        // Initialize bottom-right corner
        maxVal[n-1][n-1] = mat[n-1][n-1];
        
        // Fill last row (right to left)
        for (int j = n - 2; j >= 0; j--) {
            maxVal[n-1][j] = Math.max(mat[n-1][j], maxVal[n-1][j+1]);
        }
        
        // Fill last column (bottom to top)
        for (int i = n - 2; i >= 0; i--) {
            maxVal[i][n-1] = Math.max(mat[i][n-1], maxVal[i+1][n-1]);
        }
        
        // Fill rest of the matrix and find answer simultaneously
        int result = Integer.MIN_VALUE;
        
        for (int i = n - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                // Calculate answer using current cell as (a, b)
                result = Math.max(result, maxVal[i+1][j+1] - mat[i][j]);
                
                // Update maxVal for current cell
                maxVal[i][j] = Math.max(mat[i][j], 
                               Math.max(maxVal[i+1][j], maxVal[i][j+1]));
            }
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - Single pass through the matrix
• Space Complexity: O(n^2) - For maxVal matrix

Visualization

Space Optimized Approach

We can optimize space by computing row by row from bottom:

Complexity: O(n^2) time, O(n) space

Key Takeaways

1. Precomputation reduces time complexity from O(n^4) to O(n^2)
2. Processing from bottom-right to top-left allows building maxVal incrementally
3. The recurrence: maxVal[i][j] = max(mat[i][j], maxVal[i+1][j], maxVal[i][j+1])
4. Answer is computed while building maxVal to avoid another pass
5. This technique of precomputing submatrix properties is useful in many problems
6. Space can be optimized to O(n) with careful implementation