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>\nThe program should do only ONE traversal of the matrix. i.e. expected time complexity is O(n2<\/sup>)<\/p>\nA 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[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20A%20Naive%20method%20to%20find%20maximum%20value%20of%20mat1%5Bd%5D%0A%2F%2F%20-%20ma%5Ba%5D%5Bb%5D%20such%20that%20c%20%3E%20a%20and%20d%20%3E%20b%0A%23include%20%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%23define%20N%205%0A%20%0A%2F%2F%20The%20function%20returns%20maximum%20value%20A(c%2Cd)%20-%20A(a%2Cb)%0A%2F%2F%20over%20all%20choices%20of%20indexes%20such%20that%20both%20c%20%3E%20a%0A%2F%2F%20and%20d%20%3E%20b.%0Aint%20findMaxValue(int%20mat%5B%5D%5BN%5D)%0A%7B%0A%20%20%20%20%2F%2F%20stores%20maximum%20value%0A%20%20%20%20int%20maxValue%20%3D%20INT_MIN%3B%0A%20%0A%20%20%20%20%2F%2F%20Consider%20all%20possible%20pairs%20mat%5Ba%5D%5Bb%5D%20and%0A%20%20%20%20%2F%2F%20mat1%5Bd%5D%0A%20%20%20%20for%20(int%20a%20%3D%200%3B%20a%20%3C%20N%20-%201%3B%20a%2B%2B)%0A%20%20%20%20%20%20for%20(int%20b%20%3D%200%3B%20b%20%3C%20N%20-%201%3B%20b%2B%2B)%0A%20%20%20%20%20%20%20%20%20for%20(int%20c%20%3D%20a%20%2B%201%3B%20c%20%3C%20N%3B%20c%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20for%20(int%20d%20%3D%20b%20%2B%201%3B%20d%20%3C%20N%3B%20d%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(maxValue%20%3C%20(mat1%5Bd%5D%20-%20mat%5Ba%5D%5Bb%5D))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20maxValue%20%3D%20mat1%5Bd%5D%20-%20mat%5Ba%5D%5Bb%5D%3B%0A%20%0A%20%20%20%20return%20maxValue%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20int%20mat%5BN%5D%5BN%5D%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%201%2C%202%2C%20-1%2C%20-4%2C%20-20%20%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%20-8%2C%20-3%2C%204%2C%202%2C%201%20%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%203%2C%208%2C%206%2C%201%2C%203%20%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%20-4%2C%20-1%2C%201%2C%207%2C%20-6%20%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%200%2C%20-4%2C%2010%2C%20-5%2C%201%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%3B%0A%20%20%20%20cout%20%3C%3C%20%22Maximum%20Value%20is%20%22%0A%20%20%20%20%20%20%20%20%20%3C%3C%20findMaxValue(mat)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC++ Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\nOutput:<\/strong><\/p>\nMaximum Value is 18\r\n\r\n<\/pre>\nThe 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[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20An%20efficient%20method%20to%20find%20maximum%20value%20of%20mat1%5Bd%5D%0A%2F%2F%20-%20ma%5Ba%5D%5Bb%5D%20such%20that%20c%20%3E%20a%20and%20d%20%3E%20b%0A%23include%20%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%23define%20N%205%0A%20%0A%2F%2F%20The%20function%20returns%20maximum%20value%20A(c%2Cd)%20-%20A(a%2Cb)%0A%2F%2F%20over%20all%20choices%20of%20indexes%20such%20that%20both%20c%20%3E%20a%0A%2F%2F%20and%20d%20%3E%20b.%0Aint%20findMaxValue(int%20mat%5B%5D%5BN%5D)%0A%7B%0A%20%20%20%20%2F%2Fstores%20maximum%20value%0A%20%20%20%20int%20maxValue%20%3D%20INT_MIN%3B%0A%20%0A%20%20%20%20%2F%2F%20maxArr%5Bi%5D%5Bj%5D%20stores%20max%20of%20elements%20in%20matrix%0A%20%20%20%20%2F%2F%20from%20(i%2C%20j)%20to%20(N-1%2C%20N-1)%0A%20%20%20%20int%20maxArr%5BN%5D%5BN%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20last%20element%20of%20maxArr%20will%20be%20same\u2019s%20as%20of%0A%20%20%20%20%2F%2F%20the%20input%20matrix%0A%20%20%20%20maxArr%5BN-1%5D%5BN-1%5D%20%3D%20mat%5BN-1%5D%5BN-1%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20preprocess%20last%20row%0A%20%20%20%20int%20maxv%20%3D%20mat%5BN-1%5D%5BN-1%5D%3B%20%20%2F%2F%20Initialize%20max%0A%20%20%20%20for%20(int%20j%20%3D%20N%20-%202%3B%20j%20%3E%3D%200%3B%20j\u2013)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(mat%5BN-1%5D%5Bj%5D%20%3E%20maxv)%0A%20%20%20%20%20%20%20%20%20%20%20%20maxv%20%3D%20mat%5BN%20-%201%5D%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20maxArr%5BN-1%5D%5Bj%5D%20%3D%20maxv%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20preprocess%20last%20column%0A%20%20%20%20maxv%20%3D%20mat%5BN%20-%201%5D%5BN%20-%201%5D%3B%20%20%2F%2F%20Initialize%20max%0A%20%20%20%20for%20(int%20i%20%3D%20N%20-%202%3B%20i%20%3E%3D%200%3B%20i\u2013)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(mat%5Bi%5D%5BN%20-%201%5D%20%3E%20maxv)%0A%20%20%20%20%20%20%20%20%20%20%20%20maxv%20%3D%20mat%5Bi%5D%5BN%20-%201%5D%3B%0A%20%20%20%20%20%20%20%20maxArr%5Bi%5D%5BN%20-%201%5D%20%3D%20maxv%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20preprocess%20rest%20of%20the%20matrix%20from%20bottom%0A%20%20%20%20for%20(int%20i%20%3D%20N-2%3B%20i%20%3E%3D%200%3B%20i\u2013)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20for%20(int%20j%20%3D%20N-2%3B%20j%20%3E%3D%200%3B%20j\u2013)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Update%20maxValue%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(maxArr%5Bi%2B1%5D%5Bj%2B1%5D%20-%20mat%5Bi%5D%5Bj%5D%20%3E%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20maxValue)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20maxValue%20%3D%20maxArr%5Bi%20%2B%201%5D%5Bj%20%2B%201%5D%20-%20mat%5Bi%5D%5Bj%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20set%20maxArr%20(i%2C%20j)%0A%20%20%20%20%20%20%20%20%20%20%20%20maxArr%5Bi%5D%5Bj%5D%20%3D%20max(mat%5Bi%5D%5Bj%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20max(maxArr%5Bi%5D%5Bj%20%2B%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20maxArr%5Bi%20%2B%201%5D%5Bj%5D)%20)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20maxValue%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20int%20mat%5BN%5D%5BN%5D%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%201%2C%202%2C%20-1%2C%20-4%2C%20-20%20%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%20-8%2C%20-3%2C%204%2C%202%2C%201%20%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%203%2C%208%2C%206%2C%201%2C%203%20%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%20-4%2C%20-1%2C%201%2C%207%2C%20-6%20%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%200%2C%20-4%2C%2010%2C%20-5%2C%201%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%3B%0A%20%20%20%20cout%20%3C%3C%20%22Maximum%20Value%20is%20%22%0A%20%20%20%20%20%20%20%20%20%3C%3C%20findMaxValue(mat)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC++ Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\nOutput:<\/p>\n
Maximum Value is 18<\/pre>\nIf 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}]}}