Find the pair with maximum sum in a matrix
The problem at hand is to find the pair of elements in a given matrix that has the maximum sum. We need to search for two elements (one from each row) such that their sum is the largest among all pairs in the matrix.
Problem Statement and Example
Consider the following matrix:
2 6 9 5
-3 7 -5 10
1 0 6 3
-2 16 4 -8
1 6 -7 -6The pair of elements with the maximum sum in this matrix is (16, 10), and their sum is 26.
Idea to Solve the Problem
To find the pair with the maximum sum in the matrix, we can follow the following approach:
- Initialize two variables, 'p1' and 'p2', to hold the largest and second-largest elements, respectively. Set both variables to the minimum possible integer value to handle negative elements in the matrix.
- Iterate through each element of the matrix.
- If the current element is greater than 'p1', update 'p2' to the current value of 'p1' and update 'p1' to the current element value.
- If the current element is greater than 'p2' but not greater than 'p1', update 'p2' to the current element value.
- After iterating through the entire matrix, the variables 'p1' and 'p2' will hold the largest and second-largest elements, respectively, and we can find the maximum sum pair.
Pseudocode
maxPair(matrix, r, c):
p1 = INT_MIN
p2 = INT_MIN
for i from 0 to r:
for j from 0 to c:
if matrix[i][j] > p1:
p2 = p1
p1 = matrix[i][j]
else if matrix[i][j] > p2:
p2 = matrix[i][j]
print "Max Sum Pair (" + p1 + "," + p2 + ") : " + (p1 + p2)Algorithm Explanation
- The 'maxPair' function takes 'matrix', 'r', and 'c' as input parameters. 'matrix' is the 2D matrix, and 'r' and 'c' are the number of rows and columns in the matrix, respectively.
- The function initializes 'p1' and 'p2' to the minimum integer value using the constant 'INT_MIN'.
- It iterates through each element of the matrix using two nested loops.
- For each element, it compares it with 'p1'. If the current element is greater than 'p1', it updates 'p2' to the current value of 'p1' and 'p1' to the current element value.
- If the current element is greater than 'p2' but not greater than 'p1', it updates 'p2' to the current element value.
- After iterating through the entire matrix, 'p1' and 'p2' will hold the largest and second-largest elements, respectively.
- The function then prints the maximum sum pair, which is the pair of elements with values 'p1' and 'p2', and their sum is '(p1 + p2)'.
Code Solution
// C Program
// Find the pair with maximum sum 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("%5d", matrix[i][j]);
}
printf("\n");
}
printf("\n");
}
// Find the pair with is maximum sum
void maxPair(int matrix[R][C])
{
int p1 = INT_MIN;
int p2 = INT_MIN;
// 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 (matrix[i][j] > p1)
{
// When get new largest element
p2 = p1;
p1 = matrix[i][j];
}
else if (matrix[i][j] > p2)
{
p2 = matrix[i][j];
}
}
}
// Display the calculated resultant pair
printf(" Pair (%d %d) : %d \n", p1, p2, (p1 + p2));
}
int main(int argc, char
const *argv[])
{
// Define matrix of an integer elements
int matrix[R][C] =
{
{2, 6, 9, 5 },
{-3, 7, -5, 10 },
{1, 0, 6, 3 },
{-2, 16, 4, -8 },
{1, 6, -7, -6 }
};
printMatrix(matrix);
maxPair(matrix);
return 0;
}Output
2 6 9 5
-3 7 -5 10
1 0 6 3
-2 16 4 -8
1 6 -7 -6
Pair (16 10) : 26/*
Java program
Find the pair with maximum sum 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("\t" + matrix[i][j] );
}
System.out.print("\n");
}
System.out.print("\n");
}
// Find the pair with is maximum sum
public void maxPair(int[][] matrix, int r, int c)
{
int p1 = Integer.MIN_VALUE;
int p2 = Integer.MIN_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 (matrix[i][j] > p1)
{
// When get new largest element
p2 = p1;
p1 = matrix[i][j];
}
else if (matrix[i][j] > p2)
{
p2 = matrix[i][j];
}
}
}
// Display the calculated resultant pair
System.out.print(" Max Sum Pair (" + p1 + "," + p2 + ") : " + (p1 + p2) + " \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, -5, 10 },
{1, 0, 6, 3 },
{-2, 16, 4, -8 },
{1, 6, -7, -6 }
};
int r = matrix.length;
int c = matrix[0].length;
task.printMatrix(matrix,r,c);
task.maxPair(matrix,r,c);
}
}Output
2 6 9 5
-3 7 -5 10
1 0 6 3
-2 16 4 -8
1 6 -7 -6
Max Sum Pair (16,10) : 26// Include header file
#include <iostream>
#include <limits.h>
#define R 5
#define C 4
using namespace std;
/*
C++ program
Find the pair with maximum sum 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 << "\t" << matrix[i][j];
}
cout << "\n";
}
cout << "\n";
}
// Find the pair with is maximum sum
void maxPair(int matrix[R][C])
{
int p1 = INT_MIN;
int p2 = INT_MIN;
// 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 (matrix[i][j] > p1)
{
// When get new largest element
p2 = p1;
p1 = matrix[i][j];
}
else if (matrix[i][j] > p2)
{
p2 = matrix[i][j];
}
}
}
// Display the calculated resultant pair
cout << " Max Sum Pair (" << p1 << "," << p2 << ") : " << (p1 + p2) << " \n";
}
};
int main()
{
Pairs task = Pairs();
// Define matrix of an integer elements
int matrix[R][C] =
{
{2, 6, 9, 5 },
{-3, 7, -5, 10 },
{1, 0, 6, 3 },
{-2, 16, 4, -8 },
{1, 6, -7, -6 }
};
task.printMatrix(matrix);
task.maxPair(matrix);
return 0;
}Output
2 6 9 5
-3 7 -5 10
1 0 6 3
-2 16 4 -8
1 6 -7 -6
Max Sum Pair (16,10) : 26// Include namespace system
using System;
/*
C# program
Find the pair with maximum sum 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("\t" + matrix[i,j]);
}
Console.Write("\n");
}
Console.Write("\n");
}
// Find the pair with is maximum sum
public void maxPair(int[,] matrix, int r, int c)
{
int p1 = int.MinValue;
int p2 = int.MinValue;
// 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 (matrix[i,j] > p1)
{
// When get new largest element
p2 = p1;
p1 = matrix[i,j];
}
else if (matrix[i,j] > p2)
{
p2 = matrix[i,j];
}
}
}
// Display the calculated resultant pair
Console.Write(" Max Sum Pair (" + p1 + "," + p2 + ") : " + (p1 + p2) + " \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, -5, 10 },
{1, 0, 6, 3 },
{-2, 16, 4, -8 },
{1, 6, -7, -6 }
};
int r = matrix.GetLength(0);
int c = matrix.GetLength(1);
task.printMatrix(matrix, r, c);
task.maxPair(matrix, r, c);
}
}Output
2 6 9 5
-3 7 -5 10
1 0 6 3
-2 16 4 -8
1 6 -7 -6
Max Sum Pair (16,10) : 26<?php
/*
Php program
Find the pair with maximum sum 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 "\t". $matrix[$i][$j];
}
echo "\n";
}
echo "\n";
}
// Find the pair with is maximum sum
public function maxPair( & $matrix, $r, $c)
{
$p1 = -PHP_INT_MAX;
$p2 = -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 ($matrix[$i][$j] > $p1)
{
// When get new largest element
$p2 = $p1;
$p1 = $matrix[$i][$j];
}
else if ($matrix[$i][$j] > $p2)
{
$p2 = $matrix[$i][$j];
}
}
}
// Display the calculated resultant pair
echo " Max Sum Pair (". $p1 .",". $p2 .") : ". ($p1 + $p2) ." \n";
}
}
function main()
{
$task = new Pairs();
// Define matrix of an integer elements
$matrix = array(
array(2, 6, 9, 5),
array(-3, 7, -5, 10),
array(1, 0, 6, 3),
array(-2, 16, 4, -8),
array(1, 6, -7, -6)
);
$r = count($matrix);
$c = count($matrix[0]);
$task->printMatrix($matrix, $r, $c);
$task->maxPair($matrix, $r, $c);
}
main();Output
2 6 9 5
-3 7 -5 10
1 0 6 3
-2 16 4 -8
1 6 -7 -6
Max Sum Pair (16,10) : 26/*
Node Js program
Find the pair with maximum sum 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("\t" + matrix[i][j]);
}
process.stdout.write("\n");
}
process.stdout.write("\n");
}
// Find the pair with is maximum sum
maxPair(matrix, r, c)
{
var p1 = -Number.MAX_VALUE;
var p2 = -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 (matrix[i][j] > p1)
{
// When get new largest element
p2 = p1;
p1 = matrix[i][j];
}
else if (matrix[i][j] > p2)
{
p2 = matrix[i][j];
}
}
}
// Display the calculated resultant pair
process.stdout.write(" Max Sum Pair (" + p1 + "," + p2 + ") : " + (p1 + p2) + " \n");
}
}
function main()
{
var task = new Pairs();
// Define matrix of an integer elements
var matrix = [
[2, 6, 9, 5] ,
[-3, 7, -5, 10] ,
[1, 0, 6, 3] ,
[-2, 16, 4, -8] ,
[1, 6, -7, -6]
];
var r = matrix.length;
var c = matrix[0].length;
task.printMatrix(matrix, r, c);
task.maxPair(matrix, r, c);
}
main();Output
2 6 9 5
-3 7 -5 10
1 0 6 3
-2 16 4 -8
1 6 -7 -6
Max Sum Pair (16,10) : 26import sys
# Python 3 program
# Find the pair with maximum sum 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("\t", matrix[i][j], end = "")
j += 1
print(end = "\n")
i += 1
print(end = "\n")
# Find the pair with is maximum sum
def maxPair(self, matrix, r, c) :
p1 = -sys.maxsize
p2 = -sys.maxsize
i = 0
# Outer loop through by rows
while (i < r) :
j = 0
# Inner loop through by columns
while (j < c) :
if (matrix[i][j] > p1) :
# When get new largest element
p2 = p1
p1 = matrix[i][j]
elif(matrix[i][j] > p2) :
p2 = matrix[i][j]
j += 1
i += 1
# Display the calculated resultant pair
print(" Max Sum Pair (", p1 ,",", p2 ,") : ", (p1 + p2) ," ")
def main() :
task = Pairs()
# Define matrix of an integer elements
matrix = [
[2, 6, 9, 5] ,
[-3, 7, -5, 10] ,
[1, 0, 6, 3] ,
[-2, 16, 4, -8] ,
[1, 6, -7, -6]
]
r = len(matrix)
c = len(matrix[0])
task.printMatrix(matrix, r, c)
task.maxPair(matrix, r, c)
if __name__ == "__main__": main()Output
2 6 9 5
-3 7 -5 10
1 0 6 3
-2 16 4 -8
1 6 -7 -6
Max Sum Pair ( 16 , 10 ) : 26# Ruby program
# Find the pair with maximum sum 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("\t", matrix[i][j])
j += 1
end
print("\n")
i += 1
end
print("\n")
end
# Find the pair with is maximum sum
def maxPair(matrix, r, c)
p1 = -(2 ** (0. size * 8 - 2))
p2 = -(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 (matrix[i][j] > p1)
# When get new largest element
p2 = p1
p1 = matrix[i][j]
elsif(matrix[i][j] > p2)
p2 = matrix[i][j]
end
j += 1
end
i += 1
end
# Display the calculated resultant pair
print(" Max Sum Pair (", p1 ,",", p2 ,") : ", (p1 + p2) ," \n")
end
end
def main()
task = Pairs.new()
# Define matrix of an integer elements
matrix = [
[2, 6, 9, 5] ,
[-3, 7, -5, 10] ,
[1, 0, 6, 3] ,
[-2, 16, 4, -8] ,
[1, 6, -7, -6]
]
r = matrix.length
c = matrix[0].length
task.printMatrix(matrix, r, c)
task.maxPair(matrix, r, c)
end
main()Output
2 6 9 5
-3 7 -5 10
1 0 6 3
-2 16 4 -8
1 6 -7 -6
Max Sum Pair (16,10) : 26
/*
Scala program
Find the pair with maximum sum 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("\t" + matrix(i)(j));
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
// Find the pair with is maximum sum
def maxPair(matrix: Array[Array[Int]], r: Int, c: Int): Unit = {
var p1: Int = Int.MinValue;
var p2: Int = Int.MinValue;
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 (matrix(i)(j) > p1)
{
// When get new largest element
p2 = p1;
p1 = matrix(i)(j);
}
else if (matrix(i)(j) > p2)
{
p2 = matrix(i)(j);
}
j += 1;
}
i += 1;
}
// Display the calculated resultant pair
print(" Max Sum Pair (" + p1 + "," + p2 + ") : " + (p1 + p2) + " \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, -5, 10),
Array(1, 0, 6, 3),
Array(-2, 16, 4, -8),
Array(1, 6, -7, -6)
);
var r: Int = matrix.length;
var c: Int = matrix(0).length;
task.printMatrix(matrix, r, c);
task.maxPair(matrix, r, c);
}
}Output
2 6 9 5
-3 7 -5 10
1 0 6 3
-2 16 4 -8
1 6 -7 -6
Max Sum Pair (16,10) : 26/*
Swift 4 program
Find the pair with maximum sum 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("\t", matrix[i][j], terminator: "");
j += 1;
}
print(terminator: "\n");
i += 1;
}
print(terminator: "\n");
}
// Find the pair with is maximum sum
func maxPair(_ matrix: [[Int]], _ r: Int, _ c: Int)
{
var p1: Int = Int.min;
var p2: Int = Int.min;
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 (matrix[i][j] > p1)
{
// When get new largest element
p2 = p1;
p1 = matrix[i][j];
}
else if (matrix[i][j] > p2)
{
p2 = matrix[i][j];
}
j += 1;
}
i += 1;
}
// Display the calculated resultant pair
print(" Max Sum Pair (", p1 ,",", p2 ,") : ", (p1 + p2) ," ");
}
}
func main()
{
let task: Pairs = Pairs();
// Define matrix of an integer elements
let matrix: [[Int]] = [
[2, 6, 9, 5] ,
[-3, 7, -5, 10] ,
[1, 0, 6, 3] ,
[-2, 16, 4, -8] ,
[1, 6, -7, -6]
];
let r: Int = matrix.count;
let c: Int = matrix[0].count;
task.printMatrix(matrix, r, c);
task.maxPair(matrix, r, c);
}
main();Output
2 6 9 5
-3 7 -5 10
1 0 6 3
-2 16 4 -8
1 6 -7 -6
Max Sum Pair ( 16 , 10 ) : 26/*
Kotlin program
Find the pair with maximum sum 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("\t" + matrix[i][j]);
j += 1;
}
print("\n");
i += 1;
}
print("\n");
}
// Find the pair with is maximum sum
fun maxPair(matrix: Array <Array<Int>> , r: Int, c: Int): Unit
{
var p1: Int = Int.MIN_VALUE;
var p2: Int = Int.MIN_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 (matrix[i][j] > p1)
{
// When get new largest element
p2 = p1;
p1 = matrix[i][j];
}
else if (matrix[i][j] > p2)
{
p2 = matrix[i][j];
}
j += 1;
}
i += 1;
}
// Display the calculated resultant pair
print(" Max Sum Pair (" + p1 + "," + p2 + ") : " + (p1 + p2) + " \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, -5, 10),
arrayOf(1, 0, 6, 3),
arrayOf(-2, 16, 4, -8),
arrayOf(1, 6, -7, -6)
);
var r: Int = matrix.count();
var c: Int = matrix[0].count();
task.printMatrix(matrix, r, c);
task.maxPair(matrix, r, c);
}Output
2 6 9 5
-3 7 -5 10
1 0 6 3
-2 16 4 -8
1 6 -7 -6
Max Sum Pair (16,10) : 26Output Explanation
The given code defines a 'Pairs' class that creates a 2D matrix, displays the matrix elements, and finds the pair with the maximum sum. The output displays the original matrix and the pair with the maximum sum as follows:
Original Matrix:
2 6 9 5
-3 7 -5 10
1 0 6 3
-2 16 4 -8
1 6 -7 -6
Max Sum Pair (16, 10) : 26Time 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 'maxPair' function iterates through each element of the matrix once to find the largest and second-largest elements. Therefore, the overall time complexity is linear in the number of elements in the matrix.
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