Pair with maximum difference in a matrix
The problem is to find a pair of elements in a given matrix such that their absolute difference is maximum among all pairs. The goal is to identify the two elements that have the largest difference in value and then calculate the absolute difference between them.
Example
Consider the following 5x4 matrix:
2 6 9 5
3 7 15 10
1 0 6 3
-2 -14 4 13
11 6 12 8In this matrix, the maximum difference pair is (15, -14) with an absolute difference of 29.
Idea to Solve the Problem
To solve this problem, we can follow these steps:
- Initialize variables
maxandminto track the maximum and minimum elements in the matrix. Initializemaxwith the smallest possible integer value (INT_MIN) andminwith the largest possible integer value (INT_MAX). - Iterate through each element of the matrix:
a. If the current element is greater than
max, updatemaxwith the current element. b. If the current element is less thanmin, updateminwith the current element. - Calculate the absolute difference between
maxandmin. - Display the calculated maximum difference pair
(max, min)along with the absolute difference.
Pseudocode
maxDifference(matrix):
max = INT_MIN
min = INT_MAX
for i from 0 to R:
for j from 0 to C:
if matrix[i][j] > max:
max = matrix[i][j]
if matrix[i][j] < min:
min = matrix[i][j]
absoluteDiff = absoluteDifference(max, min)
print "Maximum difference Pair (", max, ",", min, "):", absoluteDiff
absoluteDiff(a, b):
result = a - b
if result < 0:
return -result
else:
return result
main:
matrix = {
{2, 6, 9, 5},
{3, 7, 15, 10},
{1, 0, 6, 3},
{-2, -14, 4, 13},
{11, 6, 12, 8}
}
printMatrix(matrix)
maxDifference(matrix)Code Solution
// C Program
// Pair with maximum difference in a matrix
#include <stdio.h>
#include <limits.h>
#define R 5
#define C 4
// Displaying of the matrix elements
void printMatrix(int matrix[R][C])
{
// Outer loop through by rows
for (int i = 0; i < R; ++i)
{
// Inner loop through by columns
for (int j = 0; j < C; ++j)
{
// Display element value
printf("%d\t", matrix[i][j]);
}
printf("\n");
}
printf("\n");
}
int absoluteDiff(int a, int b)
{
int result = a - b;
if(result < 0)
{
return -result;
}
else
{
return result;
}
}
// Find the pair with is difference sum
void maxDifference(int matrix[R][C])
{
int max = INT_MIN;
int min = INT_MAX;
// Outer loop through by rows
for (int i = 0; i < R; ++i)
{
// Inner loop through by columns
for (int j = 0; j < C; ++j)
{
if(max < matrix[i][j])
{
// Get new max element
max = matrix[i][j];
}
else if( min > matrix[i][j] )
{
// Get new min element
min = matrix[i][j];
}
}
}
// Display the calculated resultant pair
printf(" Maximum difference Pair (%d,%d) : %d \n",max,min,absoluteDiff(max , min));
}
int main(int argc, char const *argv[])
{
// Define matrix of an integer elements
int matrix[R][C] =
{
{2, 6, 9, 5 },
{3, 7, 15, 10 },
{1, 0, 6, 3 },
{-2, -14, 4, 13 },
{11, 6, 12, 8 }
};
printMatrix(matrix);
maxDifference(matrix);
return 0;
}Output
2 6 9 5
3 7 15 10
1 0 6 3
-2 -14 4 13
11 6 12 8
Maximum difference Pair (15,-14) : 29/*
Java program
Pair with maximum difference in a matrix
*/
public class Pairs
{
// Displaying of the matrix elements
public void printMatrix(int[][] matrix, int r, int c)
{
// Outer loop through by rows
for (int i = 0; i < r; ++i)
{
// Inner loop through by columns
for (int j = 0; j < c; ++j)
{
// Display element value
System.out.print(" " + matrix[i][j] +"\t" );
}
System.out.print("\n");
}
System.out.print("\n");
}
public int absoluteDiff(int a, int b)
{
int result = a - b;
if (result < 0)
{
return -result;
}
else
{
return result;
}
}
// Find the pair with is difference sum
public void maxDifference(int[][] matrix,int r, int c)
{
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
// Outer loop through by rows
for (int i = 0; i < r; ++i)
{
// Inner loop through by columns
for (int j = 0; j < c; ++j)
{
if (max < matrix[i][j])
{
// Get new max element
max = matrix[i][j];
}
else if (min > matrix[i][j])
{
// Get new min element
min = matrix[i][j];
}
}
}
// Display the calculated resultant pair
System.out.print(" Maximum difference Pair (" + max + "," + min + ") : " + absoluteDiff(max, min) + " \n");
}
public static void main(String[] args)
{
Pairs task = new Pairs();
// Define matrix of an integer elements
int[][] matrix =
{
{2, 6, 9, 5 },
{3, 7, 15, 10 },
{1, 0, 6, 3 },
{-2, -14, 4, 13 },
{11, 6, 12, 8 }
};
int r = matrix.length;
int c = matrix[0].length;
task.printMatrix(matrix,r,c);
task.maxDifference(matrix,r,c);
}
}
Output
2 6 9 5
3 7 15 10
1 0 6 3
-2 -14 4 13
11 6 12 8
Maximum difference Pair (15,-14) : 29// Include header file
#include <iostream>
#include <limits.h>
#define R 5
#define C 4
using namespace std;
/*
C++ program
Pair with maximum difference in a matrix
*/
class Pairs
{
public:
// Displaying of the matrix elements
void printMatrix(int matrix[R][C])
{
// Outer loop through by rows
for (int i = 0; i < R; ++i)
{
// Inner loop through by columns
for (int j = 0; j < C; ++j)
{
// Display element value
cout << "" << matrix[i][j] << "\t";
}
cout << "\n";
}
cout << "\n";
}
int absoluteDiff(int a, int b)
{
int result = a - b;
if (result < 0)
{
return -result;
}
else
{
return result;
}
}
// Find the pair with is difference sum
void maxDifference(int matrix[R][C])
{
int max = INT_MIN;
int min = INT_MAX;
// Outer loop through by rows
for (int i = 0; i < R; ++i)
{
// Inner loop through by columns
for (int j = 0; j < C; ++j)
{
if (max < matrix[i][j])
{
// Get new max element
max = matrix[i][j];
}
else if (min > matrix[i][j])
{
// Get new min element
min = matrix[i][j];
}
}
}
// Display the calculated resultant pair
cout << " Maximum difference Pair (" << max << "," << min << ") : " << this->absoluteDiff(max, min) << " \n";
}
};
int main()
{
Pairs task = Pairs();
// Define matrix of an integer elements
int matrix[R][C] =
{
{2, 6, 9, 5 },
{3, 7, 15, 10 },
{1, 0, 6, 3 },
{-2, -14, 4, 13 },
{11, 6, 12, 8 }
};
task.printMatrix(matrix);
task.maxDifference(matrix);
return 0;
}Output
2 6 9 5
3 7 15 10
1 0 6 3
-2 -14 4 13
11 6 12 8
Maximum difference Pair (15,-14) : 29// Include namespace system
using System;
/*
C# program
Pair with maximum difference in a matrix
*/
public class Pairs
{
// Displaying of the matrix elements
public void printMatrix(int[,] matrix, int r, int c)
{
// Outer loop through by rows
for (int i = 0; i < r; ++i)
{
// Inner loop through by columns
for (int j = 0; j < c; ++j)
{
// Display element value
Console.Write(" " + matrix[i,j] + "\t");
}
Console.Write("\n");
}
Console.Write("\n");
}
public int absoluteDiff(int a, int b)
{
int result = a - b;
if (result < 0)
{
return -result;
}
else
{
return result;
}
}
// Find the pair with is difference sum
public void maxDifference(int[,] matrix, int r, int c)
{
int max = int.MinValue;
int min = int.MaxValue;
// Outer loop through by rows
for (int i = 0; i < r; ++i)
{
// Inner loop through by columns
for (int j = 0; j < c; ++j)
{
if (max < matrix[i,j])
{
// Get new max element
max = matrix[i,j];
}
else if (min > matrix[i,j])
{
// Get new min element
min = matrix[i,j];
}
}
}
// Display the calculated resultant pair
Console.Write(" Maximum difference Pair (" + max + "," + min + ") : " + absoluteDiff(max, min) + " \n");
}
public static void Main(String[] args)
{
Pairs task = new Pairs();
// Define matrix of an integer elements
int[,] matrix = {
{
2 , 6 , 9 , 5
} , {
3 , 7 , 15 , 10
} , {
1 , 0 , 6 , 3
} , {
-2 , -14 , 4 , 13
} , {
11 , 6 , 12 , 8
}
};
int r = matrix.GetLength(0);
int c = matrix.GetLength(1);
task.printMatrix(matrix, r, c);
task.maxDifference(matrix, r, c);
}
}Output
2 6 9 5
3 7 15 10
1 0 6 3
-2 -14 4 13
11 6 12 8
Maximum difference Pair (15,-14) : 29<?php
/*
Php program
Pair with maximum difference in a matrix
*/
class Pairs
{
// Displaying of the matrix elements
public function printMatrix( & $matrix, $r, $c)
{
// Outer loop through by rows
for ($i = 0; $i < $r; ++$i)
{
// Inner loop through by columns
for ($j = 0; $j < $c; ++$j)
{
// Display element value
echo " ". $matrix[$i][$j] ."\t";
}
echo "\n";
}
echo "\n";
}
public function absoluteDiff($a, $b)
{
$result = $a - $b;
if ($result < 0)
{
return -$result;
}
else
{
return $result;
}
}
// Find the pair with is difference sum
public function maxDifference( & $matrix, $r, $c)
{
$max = -PHP_INT_MAX;
$min = PHP_INT_MAX;
// Outer loop through by rows
for ($i = 0; $i < $r; ++$i)
{
// Inner loop through by columns
for ($j = 0; $j < $c; ++$j)
{
if ($max < $matrix[$i][$j])
{
// Get new max element
$max = $matrix[$i][$j];
}
else if ($min > $matrix[$i][$j])
{
// Get new min element
$min = $matrix[$i][$j];
}
}
}
// Display the calculated resultant pair
echo " Maximum difference Pair (". $max .",". $min .") : ". $this->absoluteDiff($max, $min) ." \n";
}
}
function main()
{
$task = new Pairs();
// Define matrix of an integer elements
$matrix = array(
array(2, 6, 9, 5),
array(3, 7, 15, 10),
array(1, 0, 6, 3),
array(-2, -14, 4, 13),
array(11, 6, 12, 8)
);
$r = count($matrix);
$c = count($matrix[0]);
$task->printMatrix($matrix, $r, $c);
$task->maxDifference($matrix, $r, $c);
}
main();Output
2 6 9 5
3 7 15 10
1 0 6 3
-2 -14 4 13
11 6 12 8
Maximum difference Pair (15,-14) : 29/*
Node Js program
Pair with maximum difference in a matrix
*/
class Pairs
{
// Displaying of the matrix elements
printMatrix(matrix, r, c)
{
// Outer loop through by rows
for (var i = 0; i < r; ++i)
{
// Inner loop through by columns
for (var j = 0; j < c; ++j)
{
// Display element value
process.stdout.write(" " + matrix[i][j] + "\t");
}
process.stdout.write("\n");
}
process.stdout.write("\n");
}
absoluteDiff(a, b)
{
var result = a - b;
if (result < 0)
{
return -result;
}
else
{
return result;
}
}
// Find the pair with is difference sum
maxDifference(matrix, r, c)
{
var max = -Number.MAX_VALUE;
var min = Number.MAX_VALUE;
// Outer loop through by rows
for (var i = 0; i < r; ++i)
{
// Inner loop through by columns
for (var j = 0; j < c; ++j)
{
if (max < matrix[i][j])
{
// Get new max element
max = matrix[i][j];
}
else if (min > matrix[i][j])
{
// Get new min element
min = matrix[i][j];
}
}
}
// Display the calculated resultant pair
process.stdout.write(" Maximum difference Pair (" + max + "," + min + ") : " + this.absoluteDiff(max, min) + " \n");
}
}
function main()
{
var task = new Pairs();
// Define matrix of an integer elements
var matrix = [
[2, 6, 9, 5] ,
[3, 7, 15, 10] ,
[1, 0, 6, 3] ,
[-2, -14, 4, 13] ,
[11, 6, 12, 8]
];
var r = matrix.length;
var c = matrix[0].length;
task.printMatrix(matrix, r, c);
task.maxDifference(matrix, r, c);
}
main();Output
2 6 9 5
3 7 15 10
1 0 6 3
-2 -14 4 13
11 6 12 8
Maximum difference Pair (15,-14) : 29import sys
# Python 3 program
# Pair with maximum difference in a matrix
class Pairs :
# Displaying of the matrix elements
def printMatrix(self, matrix, r, c) :
i = 0
# Outer loop through by rows
while (i < r) :
j = 0
# Inner loop through by columns
while (j < c) :
# Display element value
print(matrix[i][j] , end = "\t")
j += 1
print(end = "\n")
i += 1
print(end = "\n")
def absoluteDiff(self, a, b) :
result = a - b
if (result < 0) :
return -result
else :
return result
# Find the pair with is difference sum
def maxDifference(self, matrix, r, c) :
max = -sys.maxsize
min = sys.maxsize
i = 0
# Outer loop through by rows
while (i < r) :
j = 0
# Inner loop through by columns
while (j < c) :
if (max < matrix[i][j]) :
# Get new max element
max = matrix[i][j]
elif(min > matrix[i][j]) :
# Get new min element
min = matrix[i][j]
j += 1
i += 1
# Display the calculated resultant pair
print(" Maximum difference Pair (", max ,",", min ,") : ", self.absoluteDiff(max, min) ," ")
def main() :
task = Pairs()
# Define matrix of an integer elements
matrix = [
[2, 6, 9, 5] ,
[3, 7, 15, 10] ,
[1, 0, 6, 3] ,
[-2, -14, 4, 13] ,
[11, 6, 12, 8]
]
r = len(matrix)
c = len(matrix[0])
task.printMatrix(matrix, r, c)
task.maxDifference(matrix, r, c)
if __name__ == "__main__": main()Output
2 6 9 5
3 7 15 10
1 0 6 3
-2 -14 4 13
11 6 12 8
Maximum difference Pair ( 15 , -14 ) : 29# Ruby program
# Pair with maximum difference in a matrix
class Pairs
# Displaying of the matrix elements
def printMatrix(matrix, r, c)
i = 0
# Outer loop through by rows
while (i < r)
j = 0
# Inner loop through by columns
while (j < c)
# Display element value
print(" ", matrix[i][j] ,"\t")
j += 1
end
print("\n")
i += 1
end
print("\n")
end
def absoluteDiff(a, b)
result = a - b
if (result < 0)
return -result
else
return result
end
end
# Find the pair with is difference sum
def maxDifference(matrix, r, c)
max = -(2 ** (0. size * 8 - 2))
min = (2 ** (0. size * 8 - 2))
i = 0
# Outer loop through by rows
while (i < r)
j = 0
# Inner loop through by columns
while (j < c)
if (max < matrix[i][j])
# Get new max element
max = matrix[i][j]
elsif(min > matrix[i][j])
# Get new min element
min = matrix[i][j]
end
j += 1
end
i += 1
end
# Display the calculated resultant pair
print(" Maximum difference Pair (", max ,",", min ,") : ", self.absoluteDiff(max, min) ," \n")
end
end
def main()
task = Pairs.new()
# Define matrix of an integer elements
matrix = [
[2, 6, 9, 5] ,
[3, 7, 15, 10] ,
[1, 0, 6, 3] ,
[-2, -14, 4, 13] ,
[11, 6, 12, 8]
]
r = matrix.length
c = matrix[0].length
task.printMatrix(matrix, r, c)
task.maxDifference(matrix, r, c)
end
main()Output
2 6 9 5
3 7 15 10
1 0 6 3
-2 -14 4 13
11 6 12 8
Maximum difference Pair (15,-14) : 29
/*
Scala program
Pair with maximum difference in a matrix
*/
class Pairs
{
// Displaying of the matrix elements
def printMatrix(matrix: Array[Array[Int]], r: Int, c: Int): Unit = {
var i: Int = 0;
// Outer loop through by rows
while (i < r)
{
var j: Int = 0;
// Inner loop through by columns
while (j < c)
{
// Display element value
print(" " + matrix(i)(j) + "\t");
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
def absoluteDiff(a: Int, b: Int): Int = {
var result: Int = a - b;
if (result < 0)
{
return -result;
}
else
{
return result;
}
}
// Find the pair with is difference sum
def maxDifference(matrix: Array[Array[Int]], r: Int, c: Int): Unit = {
var max: Int = Int.MinValue;
var min: Int = Int.MaxValue;
var i: Int = 0;
// Outer loop through by rows
while (i < r)
{
var j: Int = 0;
// Inner loop through by columns
while (j < c)
{
if (max < matrix(i)(j))
{
// Get new max element
max = matrix(i)(j);
}
else if (min > matrix(i)(j))
{
// Get new min element
min = matrix(i)(j);
}
j += 1;
}
i += 1;
}
// Display the calculated resultant pair
print(" Maximum difference Pair (" + max + "," + min + ") : " + this.absoluteDiff(max, min) + " \n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Pairs = new Pairs();
// Define matrix of an integer elements
var matrix: Array[Array[Int]] = Array(
Array(2, 6, 9, 5),
Array(3, 7, 15, 10),
Array(1, 0, 6, 3),
Array(-2, -14, 4, 13),
Array(11, 6, 12, 8)
);
var r: Int = matrix.length;
var c: Int = matrix(0).length;
task.printMatrix(matrix, r, c);
task.maxDifference(matrix, r, c);
}
}Output
2 6 9 5
3 7 15 10
1 0 6 3
-2 -14 4 13
11 6 12 8
Maximum difference Pair (15,-14) : 29/*
Swift 4 program
Pair with maximum difference in a matrix
*/
class Pairs
{
// Displaying of the matrix elements
func printMatrix(_ matrix: [[Int]], _ r: Int, _ c: Int)
{
var i: Int = 0;
// Outer loop through by rows
while (i < r)
{
var j: Int = 0;
// Inner loop through by columns
while (j < c)
{
// Display element value
print(matrix[i][j] , terminator: "\t");
j += 1;
}
print(terminator: "\n");
i += 1;
}
print(terminator: "\n");
}
func absoluteDiff(_ a: Int, _ b: Int)->Int
{
let result: Int = a - b;
if (result < 0)
{
return -result;
}
else
{
return result;
}
}
// Find the pair with is difference sum
func maxDifference(_ matrix: [[Int]], _ r: Int, _ c: Int)
{
var max: Int = Int.min;
var min: Int = Int.max;
var i: Int = 0;
// Outer loop through by rows
while (i < r)
{
var j: Int = 0;
// Inner loop through by columns
while (j < c)
{
if (max < matrix[i][j])
{
// Get new max element
max = matrix[i][j];
}
else if (min > matrix[i][j])
{
// Get new min element
min = matrix[i][j];
}
j += 1;
}
i += 1;
}
// Display the calculated resultant pair
print(" Maximum difference Pair (", max ,",", min ,") : ", self.absoluteDiff(max, min) ," ");
}
}
func main()
{
let task: Pairs = Pairs();
// Define matrix of an integer elements
let matrix: [[Int]] = [
[2, 6, 9, 5] ,
[3, 7, 15, 10] ,
[1, 0, 6, 3] ,
[-2, -14, 4, 13] ,
[11, 6, 12, 8]
];
let r: Int = matrix.count;
let c: Int = matrix[0].count;
task.printMatrix(matrix, r, c);
task.maxDifference(matrix, r, c);
}
main();Output
2 6 9 5
3 7 15 10
1 0 6 3
-2 -14 4 13
11 6 12 8
Maximum difference Pair ( 15 , -14 ) : 29/*
Kotlin program
Pair with maximum difference in a matrix
*/
class Pairs
{
// Displaying of the matrix elements
fun printMatrix(matrix: Array <Array<Int>> , r: Int, c: Int): Unit
{
var i: Int = 0;
// Outer loop through by rows
while (i < r)
{
var j: Int = 0;
// Inner loop through by columns
while (j < c)
{
// Display element value
print(" " + matrix[i][j] + "\t");
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
fun absoluteDiff(a: Int, b: Int): Int
{
var result: Int = a - b;
if (result < 0)
{
return -result;
}
else
{
return result;
}
}
// Find the pair with is difference sum
fun maxDifference(matrix: Array < Array < Int >> , r: Int, c: Int): Unit
{
var max: Int = Int.MIN_VALUE;
var min: Int = Int.MAX_VALUE;
var i: Int = 0;
// Outer loop through by rows
while (i < r)
{
var j: Int = 0;
// Inner loop through by columns
while (j < c)
{
if (max < matrix[i][j])
{
// Get new max element
max = matrix[i][j];
}
else if (min > matrix[i][j])
{
// Get new min element
min = matrix[i][j];
}
j += 1;
}
i += 1;
}
// Display the calculated resultant pair
print(" Maximum difference Pair (" + max + "," + min + ") : " + this.absoluteDiff(max, min) + " \n");
}
}
fun main(args: Array <String> ): Unit
{
var task: Pairs = Pairs();
// Define matrix of an integer elements
var matrix: Array <Array<Int >> = arrayOf(
arrayOf(2, 6, 9, 5),
arrayOf(3, 7, 15, 10),
arrayOf(1, 0, 6, 3),
arrayOf(-2, -14, 4, 13),
arrayOf(11, 6, 12, 8));
var r: Int = matrix.count();
var c: Int = matrix[0].count();
task.printMatrix(matrix, r, c);
task.maxDifference(matrix, r, c);
}Output
2 6 9 5
3 7 15 10
1 0 6 3
-2 -14 4 13
11 6 12 8
Maximum difference Pair (15,-14) : 29Output Explanation
The C code implements the above algorithm to find the maximum difference pair in the given matrix.
It iterates through each element of the matrix and updates the max and min variables
accordingly. After finding the maximum and minimum elements, it calculates the absolute difference between them and
displays the result. The output of the code is "Maximum difference Pair (15, -14): 29," which is the maximum
absolute difference between any pair of elements in the matrix.
Time Complexity
The time complexity of the provided solution is O(R * C), where R is the number of rows and C is the number of
columns in the matrix. The maxDifference function iterates through each element of the matrix using two
nested loops, resulting in a total of R * C iterations. Therefore, the time complexity is O(R * C).
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment