Find a specific pair in Matrix

Given an n x n matrix mat[n][n] of integers, 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:

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

The program should do only ONE traversal of the matrix. i.e. expected time complexity is O(n²)

A simple solution would be to apply Brute-Force. For all values mat(a, b) in the matrix, we find mat(c, d) that has maximum value such that c > a and d > b and keeps on updating maximum value found so far. We finally return the maximum value.

Below is its implementation.

C++

// A Naive method to find maximum value of mat[d][e] 
// - ma[a][b] such that d > a and e > b 
#include <bits/stdc++.h> 
using namespace std; 
#define N 5 
  
// The function returns maximum value A(d,e) - A(a,b) 
// over all choices of indexes such that both d > a 
// and e > b. 
int findMaxValue(int mat[][N]) 
{ 
    // stores maximum value 
    int maxValue = INT_MIN; 
  
    // Consider all possible pairs mat[a][b] and 
    // mat[d][e] 
    for (int a = 0; a < N - 1; a++) 
    for (int b = 0; b < N - 1; b++) 
        for (int d = a + 1; d < N; d++) 
        for (int e = b + 1; e < N; e++) 
            if (maxValue < (mat[d][e] - mat[a][b])) 
                maxValue = mat[d][e] - mat[a][b]; 
  
    return maxValue; 
} 
  
// Driver program to test above function 
int main() 
{ 
int 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 } 
            }; 
    cout << "Maximum Value is "
        << findMaxValue(mat); 
  
    return 0; 
} 

Java

// A Naive method to find maximum value of mat1[d][e] 
// - ma[a][b] such that d > a and e > b 
import java.io.*; 
import java.util.*; 
   
class GFG  
{ 
    // The function returns maximum value A(d,e) - A(a,b) 
    // over all choices of indexes such that both d > a 
    // and e > b. 
    static int findMaxValue(int N,int mat[][]) 
    { 
        // stores maximum value 
        int maxValue = Integer.MIN_VALUE; 
       
        // Consider all possible pairs mat[a][b] and 
        // mat1[d][e] 
        for (int a = 0; a < N - 1; a++) 
          for (int b = 0; b < N - 1; b++) 
             for (int d = a + 1; d < N; d++) 
               for (int e = b + 1; e < N; e++) 
                  if (maxValue < (mat[d][e] - mat[a][b])) 
                      maxValue = mat[d][e] - mat[a][b]; 
       
        return maxValue; 
    } 
       
    // Driver code 
    public static void main (String[] args)  
    { 
        int N = 5; 
  
        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 } 
                   }; 
  
        System.out.print("Maximum Value is " +  
                         findMaxValue(N,mat)); 
    } 
} 
   
// This code is contributed 
// by Prakriti Gupta 

Python 3

# A Naive method to find maximum  
# value of mat[d][e] - mat[a][b] 
# such that d > a and e > b 
N = 5
  
# The function returns maximum  
# value A(d,e) - A(a,b) over  
# all choices of indexes such  
# that both d > a and e > b. 
def findMaxValue(mat): 
      
    # stores maximum value 
    maxValue = 0
  
    # Consider all possible pairs  
    # mat[a][b] and mat[d][e] 
    for a in range(N - 1): 
        for b in range(N - 1): 
            for d in range(a + 1, N): 
                for e in range(b + 1, N): 
                    if maxValue < int (mat[d][e] - 
                                       mat[a][b]): 
                        maxValue = int(mat[d][e] - 
                                       mat[a][b]); 
  
    return maxValue; 
  
# Driver Code 
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 ]]; 
         
print("Maximum Value is " + 
       str(findMaxValue(mat))) 
        
# This code is contributed  
# by ChitraNayal 

C#

// A Naive method to find maximum  
// value of mat[d][e] - mat[a][b] 
// such that d > a and e > b 
using System; 
class GFG 
{ 
      
    // The function returns 
    // maximum value A(d,e) - A(a,b) 
    // over all choices of indexes  
    // such that both d > a 
    // and e > b. 
    static int findMaxValue(int N,  
                            int [,]mat) 
    { 
          
        //stores maximum value 
        int maxValue = int.MinValue; 
      
        // Consider all possible pairs  
        // mat[a][b] and mat[d][e] 
        for (int a = 0; a< N - 1; a++) 
        for (int b = 0; b < N - 1; b++) 
            for (int d = a + 1; d < N; d++) 
            for (int e = b + 1; e < N; e++) 
                if (maxValue < (mat[d, e] -  
                                mat[a, b])) 
                    maxValue = mat[d, e] -  
                               mat[a, b]; 
  
        return maxValue; 
    } 
      
    // Driver code 
    public static void Main ()  
    { 
        int N = 5; 
  
        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}}; 
        Console.Write("Maximum Value is " +  
                      findMaxValue(N,mat)); 
    } 
} 
  
// This code is contributed  
// by ChitraNayal 

PHP

<?php 
// A Naive method to find maximum  
// value of $mat[d][e] - ma[a][b] 
// such that $d > $a and $e > $b 
$N = 5; 
  
// The function returns maximum  
// value A(d,e) - A(a,b) over  
// all choices of indexes such  
// that both $d > $a and $e > $b. 
function findMaxValue(&$mat) 
{ 
    global $N; 
      
    // stores maximum value 
    $maxValue = PHP_INT_MIN; 
  
    // Consider all possible  
    // pairs $mat[$a][$b] and 
    // $mat[$d][$e] 
    for ($a = 0; $a < $N - 1; $a++) 
    for ($b = 0; $b < $N - 1; $b++) 
        for ($d = $a + 1; $d < $N; $d++) 
        for ($e = $b + 1; $e < $N; $e++) 
            if ($maxValue < ($mat[$d][$e] -  
                             $mat[$a][$b])) 
                $maxValue = $mat[$d][$e] -  
                            $mat[$a][$b]; 
  
    return $maxValue; 
} 
  
// Driver Code 
$mat = array(array(1, 2, -1, -4, -20), 
             array(-8, -3, 4, 2, 1), 
             array(3, 8, 6, 1, 3), 
             array(-4, -1, 1, 7, -6), 
             array(0, -4, 10, -5, 1)); 
              
echo "Maximum Value is " .  
       findMaxValue($mat); 
  
// This code is contributed  
// by ChitraNayal 
?> 

Output:

Maximum Value is 18

The above program runs in O(n^4) time which is nowhere close to expected time complexity of O(n^2)

An efficient solution uses extra space. We pre-process the matrix such that index(i, j) stores max of elements in matrix from (i, j) to (N-1, N-1) and in the process keeps on updating maximum value found so far. We finally return the maximum value.

C++

// An efficient method to find maximum value of mat[d] 
// - ma[a][b] such that c > a and d > b 
#include <bits/stdc++.h> 
using namespace std; 
#define N 5 
  
// The function returns maximum value A(c,d) - A(a,b) 
// over all choices of indexes such that both c > a 
// and d > b. 
int findMaxValue(int mat[][N]) 
{ 
    //stores maximum value 
    int maxValue = INT_MIN; 
  
    // maxArr[i][j] stores max of elements in matrix 
    // from (i, j) to (N-1, N-1) 
    int maxArr[N][N]; 
  
    // last element of maxArr will be same's as of 
    // the input matrix 
    maxArr[N-1][N-1] = mat[N-1][N-1]; 
  
    // preprocess last row 
    int maxv = mat[N-1][N-1];  // Initialize max 
    for (int j = N - 2; j >= 0; j--) 
    { 
        if (mat[N-1][j] > maxv) 
            maxv = mat[N - 1][j]; 
        maxArr[N-1][j] = maxv; 
    } 
  
    // preprocess last column 
    maxv = mat[N - 1][N - 1];  // Initialize max 
    for (int i = N - 2; i >= 0; i--) 
    { 
        if (mat[i][N - 1] > maxv) 
            maxv = mat[i][N - 1]; 
        maxArr[i][N - 1] = maxv; 
    } 
  
    // preprocess rest of the matrix from bottom 
    for (int i = N-2; i >= 0; i--) 
    { 
        for (int j = N-2; j >= 0; j--) 
        { 
            // Update maxValue 
            if (maxArr[i+1][j+1] - mat[i][j] > 
                                            maxValue) 
                maxValue = maxArr[i + 1][j + 1] - mat[i][j]; 
  
            // set maxArr (i, j) 
            maxArr[i][j] = max(mat[i][j], 
                               max(maxArr[i][j + 1], 
                                   maxArr[i + 1][j]) ); 
        } 
    } 
  
    return maxValue; 
} 
  
// Driver program to test above function 
int main() 
{ 
    int 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 } 
                    }; 
    cout << "Maximum Value is " 
         << findMaxValue(mat); 
  
    return 0; 
} 

Java

// An efficient method to find maximum value of mat1[d] 
// - ma[a][b] such that c > a and d > b 
import java.io.*; 
import java.util.*; 
   
class GFG  
{ 
    // The function returns maximum value A(c,d) - A(a,b) 
    // over all choices of indexes such that both c > a 
    // and d > b. 
    static int findMaxValue(int N,int mat[][]) 
    { 
        //stores maximum value 
        int maxValue = Integer.MIN_VALUE; 
       
        // maxArr[i][j] stores max of elements in matrix 
        // from (i, j) to (N-1, N-1) 
        int maxArr[][] = new int[N][N]; 
       
        // last element of maxArr will be same's as of 
        // the input matrix 
        maxArr[N-1][N-1] = mat[N-1][N-1]; 
       
        // preprocess last row 
        int maxv = mat[N-1][N-1];  // Initialize max 
        for (int j = N - 2; j >= 0; j--) 
        { 
            if (mat[N-1][j] > maxv) 
                maxv = mat[N - 1][j]; 
            maxArr[N-1][j] = maxv; 
        } 
       
        // preprocess last column 
        maxv = mat[N - 1][N - 1];  // Initialize max 
        for (int i = N - 2; i >= 0; i--) 
        { 
            if (mat[i][N - 1] > maxv) 
                maxv = mat[i][N - 1]; 
            maxArr[i][N - 1] = maxv; 
        } 
       
        // preprocess rest of the matrix from bottom 
        for (int i = N-2; i >= 0; i--) 
        { 
            for (int j = N-2; j >= 0; j--) 
            { 
                // Update maxValue 
                if (maxArr[i+1][j+1] - mat[i][j] > maxValue) 
                    maxValue = maxArr[i + 1][j + 1] - mat[i][j]; 
       
                // set maxArr (i, j) 
                maxArr[i][j] = Math.max(mat[i][j], 
                                   Math.max(maxArr[i][j + 1], 
                                       maxArr[i + 1][j]) ); 
            } 
        } 
       
        return maxValue; 
    } 
      
    // Driver code 
    public static void main (String[] args)  
    { 
        int N = 5; 
  
        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 } 
                   }; 
  
        System.out.print("Maximum Value is " +  
                           findMaxValue(N,mat)); 
    } 
} 
   
// Contributed by Prakriti Gupta 

Python3

# An efficient method to find maximum value  
# of mat[d] - ma[a][b] such that c > a and d > b 
  
import sys 
N = 5
  
# The function returns maximum value  
# A(c,d) - A(a,b) over all choices of  
# indexes such that both c > a and d > b. 
def findMaxValue(mat): 
  
    # stores maximum value 
    maxValue = -sys.maxsize -1
  
    # maxArr[i][j] stores max of elements  
    # in matrix from (i, j) to (N-1, N-1) 
    maxArr = [[0 for x in range(N)] 
                 for y in range(N)] 
  
    # last element of maxArr will be  
    # same's as of the input matrix 
    maxArr[N - 1][N - 1] = mat[N - 1][N - 1] 
  
    # preprocess last row 
    maxv = mat[N - 1][N - 1]; # Initialize max 
    for j in range (N - 2, -1, -1): 
      
        if (mat[N - 1][j] > maxv): 
            maxv = mat[N - 1][j] 
        maxArr[N - 1][j] = maxv 
      
    # preprocess last column 
    maxv = mat[N - 1][N - 1] # Initialize max 
    for i in range (N - 2, -1, -1): 
      
        if (mat[i][N - 1] > maxv): 
            maxv = mat[i][N - 1] 
        maxArr[i][N - 1] = maxv 
  
    # preprocess rest of the matrix 
    # from bottom 
    for i in range (N - 2, -1, -1): 
      
        for j in range (N - 2, -1, -1): 
          
            # Update maxValue 
            if (maxArr[i + 1][j + 1] -
                mat[i][j] > maxValue): 
                maxValue = (maxArr[i + 1][j + 1] - 
                                       mat[i][j]) 
  
            # set maxArr (i, j) 
            maxArr[i][j] = max(mat[i][j],  
                           max(maxArr[i][j + 1],  
                               maxArr[i + 1][j])) 
          
    return maxValue 
  
# Driver Code 
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 ]] 
                      
print ("Maximum Value is", 
        findMaxValue(mat)) 
  
# This code is contributed by iAyushRaj 

C#

// An efficient method to find  
// maximum value of mat1[d] 
// - ma[a][b] such that c > a  
// and d > b 
using System; 
class GFG  { 
      
    // The function returns 
    // maximum value A(c,d) - A(a,b) 
    // over all choices of indexes  
    // such that both c > a 
    // and d > b. 
    static int findMaxValue(int N, int [,]mat) 
    { 
          
        //stores maximum value 
        int maxValue = int.MinValue; 
      
        // maxArr[i][j] stores max  
        // of elements in matrix 
        // from (i, j) to (N-1, N-1) 
        int [,]maxArr = new int[N, N]; 
      
        // last element of maxArr  
        // will be same's as of 
        // the input matrix 
        maxArr[N - 1, N - 1] = mat[N - 1,N - 1]; 
      
        // preprocess last row 
         // Initialize max 
        int maxv = mat[N - 1, N - 1]; 
        for (int j = N - 2; j >= 0; j--) 
        { 
            if (mat[N - 1, j] > maxv) 
                maxv = mat[N - 1, j]; 
            maxArr[N - 1, j] = maxv; 
        } 
      
        // preprocess last column 
        // Initialize max 
        maxv = mat[N - 1,N - 1];  
        for (int i = N - 2; i >= 0; i--) 
        { 
            if (mat[i, N - 1] > maxv) 
                maxv = mat[i,N - 1]; 
            maxArr[i,N - 1] = maxv; 
        } 
      
        // preprocess rest of the 
        // matrix from bottom 
        for (int i = N - 2; i >= 0; i--) 
        { 
            for (int j = N - 2; j >= 0; j--) 
            { 
                  
                // Update maxValue 
                if (maxArr[i + 1,j + 1] -  
                     mat[i, j] > maxValue) 
                    maxValue = maxArr[i + 1,j + 1] -  
                                         mat[i, j]; 
      
                // set maxArr (i, j) 
                maxArr[i,j] = Math.Max(mat[i, j], 
                              Math.Max(maxArr[i, j + 1], 
                              maxArr[i + 1, j]) ); 
            } 
        } 
      
        return maxValue; 
    } 
      
    // Driver code 
    public static void Main ()  
    { 
        int N = 5; 
  
        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 }}; 
        Console.Write("Maximum Value is " +  
                        findMaxValue(N,mat)); 
    } 
} 
  
// This code is contributed by nitin mittal. 

PHP

<?php  
// An efficient method to find  
// maximum value of mat[d] - ma[a][b]  
// such that c > a and d > b 
$N = 5; 
  
// The function returns maximum  
// value A(c,d) - A(a,b) over 
// all choices of indexes such  
// that both c > a and d > b. 
function findMaxValue($mat) 
{ 
    global $N; 
      
    // stores maximum value 
    $maxValue = PHP_INT_MIN; 
  
    // maxArr[i][j] stores max  
    // of elements in matrix 
    // from (i, j) to (N-1, N-1) 
    $maxArr[$N][$N] = array(); 
  
    // last element of maxArr  
    // will be same's as of 
    // the input matrix 
    $maxArr[$N - 1][$N - 1] = $mat[$N - 1][$N - 1]; 
  
    // preprocess last row 
    $maxv = $mat[$N - 1][$N - 1]; // Initialize max 
    for ($j = $N - 2; $j >= 0; $j--) 
    { 
        if ($mat[$N - 1][$j] > $maxv) 
            $maxv = $mat[$N - 1][$j]; 
        $maxArr[$N - 1][$j] = $maxv; 
    } 
  
    // preprocess last column 
    $maxv = $mat[$N - 1][$N - 1]; // Initialize max 
    for ($i = $N - 2; $i >= 0; $i--) 
    { 
        if ($mat[$i][$N - 1] > $maxv) 
            $maxv = $mat[$i][$N - 1]; 
        $maxArr[$i][$N - 1] = $maxv; 
    } 
  
    // preprocess rest of the 
    // matrix from bottom 
    for ($i = $N - 2; $i >= 0; $i--) 
    { 
        for ($j = $N - 2; $j >= 0; $j--) 
        { 
            // Update maxValue 
            if ($maxArr[$i + 1][$j + 1] -  
                $mat[$i][$j] > $maxValue) 
                $maxValue = $maxArr[$i + 1][$j + 1] -  
                            $mat[$i][$j]; 
  
            // set maxArr (i, j) 
            $maxArr[$i][$j] = max($mat[$i][$j], 
                              max($maxArr[$i][$j + 1], 
                                  $maxArr[$i + 1][$j])); 
        } 
    } 
  
    return $maxValue; 
} 
  
// Driver Code 
$mat = array(array(1, 2, -1, -4, -20), 
             array(-8, -3, 4, 2, 1), 
             array(3, 8, 6, 1, 3), 
             array(-4, -1, 1, 7, -6), 
             array(0, -4, 10, -5, 1) 
                    ); 
echo "Maximum Value is ".  
      findMaxValue($mat); 
  
// This code is contributed  
// by ChitraNayal 
?> 

Output:

Maximum Value is 18

If we are allowed to modify of the matrix, we can avoid using extra space and use input matrix instead.

Exercise: Print index (a, b) and (c, d) as well.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above

C++

Java

Python 3

C#

PHP

C++

Java

Python3

C#

PHP

tags:

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books