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(n2)
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.
[pastacode lang=”cpp” manual=”%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” message=”C++ Program” highlight=”” provider=”manual”/] [ad type=”banner”]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.
[pastacode lang=”cpp” manual=”%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’s%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–)%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–)%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–)%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–)%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” message=”C++ Program” highlight=”” provider=”manual”/] [ad type=”banner”]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.