Find a specific pair in Matrix - GeeksforGeeks

Find a specific pair in Matrix - GeeksforGeeks
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.

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

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.

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.

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;

}

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.

int findMaxValue(int mat[][N])

{

    // stores maximum value

    int maxValue = INT_MIN;

 

    // Consider all possible pairs mat[a][b] and

    // mat1[d]

    for (int a = 0; a < N - 1; a++)

      for (int b = 0; b < N - 1; b++)

         for (int c = a + 1; c < N; c++)

           for (int d = b + 1; d < N; d++)

              if (maxValue < (mat1[d] - mat[a][b]))

                  maxValue = mat1[d] - mat[a][b];

 

    return maxValue;

}

Read full article from Find a specific pair in Matrix - GeeksforGeeks