{"id":28334,"date":"2017-12-24T16:07:41","date_gmt":"2017-12-24T10:37:41","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=28334"},"modified":"2017-12-24T16:07:41","modified_gmt":"2017-12-24T10:37:41","slug":"find-specific-pair-matrix","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/find-specific-pair-matrix\/","title":{"rendered":"C++ Programming-Find a specific pair in Matrix"},"content":{"rendered":"

Given an n x n matrix mat[n][n] of integers, find the maximum value of mat(c, d) \u2013 mat(a, b) over all choices of indexes such that both c > a and d > b.<\/p>\n

Example:<\/p>\n

Input:\r\nmat[N][N] = {{ 1, 2, -1, -4, -20 },\r\n             { -8<\/strong>, -3, 4, 2, 1 }, \r\n             { 3, 8, 6, 1, 3 },\r\n             { -4, -1, 1, 7, -6 },\r\n             { 0, -4, 10<\/strong>, -5, 1 }};\r\nOutput: 18\r\nThe maximum value is 18 as mat[4][2] \r\n- mat[1][0] = 18 has maximum difference.<\/pre>\n
The program should do only ONE traversal of the matrix. i.e. expected time complexity is O(n2<\/sup>)<\/p>\n
A simple solution<\/strong> 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.<\/p>\n
 
 C++ Program<\/span> <\/div> 
\/\/ A Naive method to find maximum value of mat1[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;     \/\/ 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;} \/\/ Driver program to test above functionint 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;}<\/code><\/pre> <\/div>\n[ad type=”banner”]\n
Output:<\/strong><\/p>\n
Maximum Value is 18\r\n\r\n<\/pre>\n
The above program runs in O(n^4) time which is nowhere close to expected time complexity of O(n^2)<\/p>\n
An efficient solution<\/strong> 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.<\/p>\n
 
 C++ Program<\/span> <\/div> 
\/\/ An efficient method to find maximum value of mat1[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 functionint 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;}<\/code><\/pre> <\/div>\n[ad type=”banner”]\n
Output:<\/p>\n
Maximum Value is 18<\/pre>\n
If we are allowed to modify of the matrix, we can avoid using extra space and use input matrix instead.<\/p>\n","protected":false},"excerpt":{"rendered":"
C++ Programming-Find a specific pair in Matrix-Matrix
\nGiven an n x n matrix mat[n][n] of integers, find the maximum value of mat(c, d) <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[83515,1,82291],"tags":[83733,83729,83730,82475,83726,83725,83728,83727,83732,83731],"class_list":["post-28334","post","type-post","status-publish","format-standard","hentry","category-c-programming-3","category-coding","category-matrix","tag-applications-of-c-programming","tag-c-program-to-find-closest-pair-of-points-in-an-array","tag-computer-science-with-c-programming","tag-count-all-distinct-pairs-with-difference-equal-to-k","tag-find-a-pair-with-the-given-difference","tag-find-a-specific-pair-in-matrix","tag-find-all-symmetric-pairs-in-it","tag-given-an-array-of-pairs","tag-matrices-and-c-code","tag-vectors"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/28334","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=28334"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/28334\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=28334"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=28334"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=28334"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}