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:
- Observation: If we fix
(c, d)
as the bottom-right element of a submatrix, then for any fixed(a, b)
wherea < c
andb < d
, the maximum value ofmat(c, d) - mat(a, b)
depends on the smallest value seen in all submatrices containing(c, d)
. - Dynamic Programming Strategy:
- Precompute the
max_matrix
so thatmax_matrix[i][j]
contains the maximum element in the submatrix starting from(i, j)
to the bottom-right corner of themat
. - Iterate over all possible
(a, b)
positions and calculate the maximum difference usingmax_matrix
. - Update the result during each iteration.
- Precompute the
- 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:
- Base Cases:
- The bottom-right cell of
max_matrix
is initialized asmat[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.
- The bottom-right cell of
- 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)
, updatemax_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)
.
- Efficiency:
- The algorithm runs in
O(n^2)
since we need to processn^2
values and compute the maximum for each cell in constant time.
- The algorithm runs in