Posted on

Maximum difference between pair in a matrix

https://www.geeksforgeeks.org/problems/maximum-difference-between-pair-in-a-matrix/

Difficulty: Hard
Accuracy: 49.36%
Submissions: 2K+Points: 8

Given an n x n matrix, mat[n][n] of integers. The task is to find the maximum value of mat(c, d)- mat(a, b) over all choices of indexes such that both c > a and d > b.

Example 1:

Input: mat[N][N] = {{ 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: The maximum value is 18 as mat[4][2] - mat[1][0] = 18 has maximum difference.

Your Task:  
You don’t need to read input or print anything. Your task is to complete the function findMaxValue() which takes a matrix mat and returns an integer as output.

Expected Time Complexity: O(n2)
Expected Auxiliary Space: O(n2)

Constraints:
1 <= n<= 103
-103<= mat[i][j] <=103

Approach:

  1. Observation: If we fix (c, d) as the bottom-right element of a submatrix, then for any fixed (a, b) where a < c and b < d, the maximum value of mat(c, d) - mat(a, b) depends on the smallest value seen in all submatrices containing (c, d).
  2. Dynamic Programming Strategy:
    • Precompute the max_matrix so that max_matrix[i][j] contains the maximum element in the submatrix starting from (i, j) to the bottom-right corner of the mat.
    • Iterate over all possible (a, b) positions and calculate the maximum difference using max_matrix.
    • Update the result during each iteration.
  3. Algorithm:
    • Start from the bottom right of the matrix and move to the top left.
    • Precompute the max_matrix while iterating.
    • Calculate the result using:
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int findMaxValue(vector<vector<int>>& mat, int n) {
    // Create an auxiliary matrix to store maximum elements
    vector<vector<int>> max_matrix(n, vector<int>(n, 0));

    // Initialize variables
    int max_diff = INT_MIN;

    // Initialize the last value of max_matrix (bottom-right corner)
    max_matrix[n - 1][n - 1] = mat[n - 1][n - 1];

    // Precompute max values for the last row
    for (int j = n - 2; j >= 0; j--) {
        max_matrix[n - 1][j] = max(mat[n - 1][j], max_matrix[n - 1][j + 1]);
    }

    // Precompute max values for the last column
    for (int i = n - 2; i >= 0; i--) {
        max_matrix[i][n - 1] = max(mat[i][n - 1], max_matrix[i + 1][n - 1]);
    }

    // Precompute the rest of the max_matrix and find the maximum difference
    for (int i = n - 2; i >= 0; i--) {
        for (int j = n - 2; j >= 0; j--) {
            // Update the maximum difference
            max_diff = max(max_diff, max_matrix[i + 1][j + 1] - mat[i][j]);

            // Update the max_matrix for position (i, j)
            max_matrix[i][j] = max(mat[i][j], max(max_matrix[i + 1][j], max_matrix[i][j + 1]));
        }
    }

    return max_diff;
}

int main() {
    vector<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 }};
    int n = mat.size();

    cout << "Maximum Difference: " << findMaxValue(mat, n) << endl;

    return 0;
}

Explanation of Code:

  1. Base Cases:
    • The bottom-right cell of max_matrix is initialized as mat[n-1][n-1] because it’s the only element in that submatrix.
    • The last row and column of max_matrix are precomputed since they only depend on the elements to their right and below, respectively.
  2. Updating the Rest of the Matrix:
    • Start from the bottom-right corner and fill up the rest of the matrix.
    • At each cell (i, j), update max_diff using the value:
max_matrix[i+1][j+1] - mat[i][j]
  • Update max_matrix[i][j] to store the maximum element in the submatrix starting at (i, j).
  1. Efficiency:
    • The algorithm runs in O(n^2) since we need to process n^2 values and compute the maximum for each cell in constant time.