Posted on by Kalkicode
Code Matrix

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  -6

The 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:

  1. 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.
  2. Iterate through each element of the matrix.
  3. If the current element is greater than 'p1', update 'p2' to the current value of 'p1' and update 'p1' to the current element value.
  4. If the current element is greater than 'p2' but not greater than 'p1', update 'p2' to the current element value.
  5. 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

  1. 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.
  2. The function initializes 'p1' and 'p2' to the minimum integer value using the constant 'INT_MIN'.
  3. It iterates through each element of the matrix using two nested loops.
  4. 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.
  5. If the current element is greater than 'p2' but not greater than 'p1', it updates 'p2' to the current element value.
  6. After iterating through the entire matrix, 'p1' and 'p2' will hold the largest and second-largest elements, respectively.
  7. 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) : 26
import 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) : 26

Output 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) : 26

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 '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.

Comment

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