Find row with maximum sum in a Matrix
Given an N*N matrix. The task is to find the index of a row with the maximum sum. That is the row whose sum of elements is maximum.
Examples:
Input : mat[][] = {
{ 1, 2, 3, 4, 5 },
{ 5, 3, 1, 4, 2 },
{ 5, 6, 7, 8, 9 },
{ 0, 6, 3, 4, 12 },
{ 9, 7, 12, 4, 3 },
};Output : Row 3 has max sum 35
Input : mat[][] = {
{ 1, 2, 3 },
{ 4, 2, 1 },
{ 5, 6, 7 },
};
Output : Row 3 has max sum 18
The idea is to traverse the matrix row-wise and find the sum of elements in each row and check for every row if current sum is greater than the maximum sum obtained till the current row and update the maximum_sum accordingly.
Algorithm:
- Define a constant N as the number of rows and columns in the matrix.
- Define a function colMaxSum that takes a 2D array of integers mat of size N*N as its input.
- Initialize two variables idx and maxSum to -1 and INT_MIN respectively.
- Traverse the matrix row-wise.
- For each row, calculate the sum of all the elements in that row.
- If the sum of the current row is greater than the current maxSum, update maxSum to be the sum of the current row and set idx to be the index of the current row.
- Return a pair of integers, with the first element being the index of the row with the maximum sum (idx) and the second element being the maximum sum (maxSum).
Pseudocode:
1. N ? number of rows and columns in the matrix 2. function colMaxSum(mat[N][N]) 3. idx ? -1 4. maxSum ? INT_MIN 5. for i from 0 to N-1 6. sum ? 0 7. for j from 0 to N-1 8. sum ? sum + mat[i][j] 9. if sum > maxSum 10. maxSum ? sum 11. idx ? i 12. return pair(idx, maxSum) 13. end function
Below is the implementation of the above approach:
C++
// C++ program to find row with // max sum in a matrix #include <bits/stdc++.h> using namespace std; #define N 5 // No of rows and column // Function to find the row with max sum pair< int , int > colMaxSum( int mat[N][N]) { // Variable to store index of row // with maximum int idx = -1; // Variable to store max sum int maxSum = INT_MIN; // Traverse matrix row wise for ( int i = 0; i < N; i++) { int sum = 0; // calculate sum of row for ( int j = 0; j < N; j++) { sum += mat[i][j]; } // Update maxSum if it is less than // current sum if (sum > maxSum) { maxSum = sum; // store index idx = i; } } pair< int , int > res; res = make_pair(idx, maxSum); // return result return res; } // Driver code int main() { int mat[N][N] = { { 1, 2, 3, 4, 5 }, { 5, 3, 1, 4, 2 }, { 5, 6, 7, 8, 9 }, { 0, 6, 3, 4, 12 }, { 9, 7, 12, 4, 3 }, }; pair< int , int > ans = colMaxSum(mat); cout << "Row " << ans.first + 1 << " has max sum " << ans.second; return 0; } |
Java
// Java program to find row with // max sum in a matrix import java.util.ArrayList; class MaxSum { public static int N; static ArrayList<Integer> colMaxSum( int mat[][]) { // Variable to store index of row // with maximum int idx = - 1 ; // Variable to store maximum sum int maxSum = Integer.MIN_VALUE; // Traverse the matrix row wise for ( int i = 0 ; i < N; i++) { int sum = 0 ; for ( int j = 0 ; j < N; j++) { sum += mat[i][j]; } // Update maxSum if it is less than // current row sum if (maxSum < sum) { maxSum = sum; // store index idx = i; } } // Arraylist to store values of index // of maximum sum and the maximum sum together ArrayList<Integer> res = new ArrayList<>(); res.add(idx); res.add(maxSum); return res; } // Driver code public static void main(String[] args) { N = 5 ; int [][] mat = { { 1 , 2 , 3 , 4 , 5 }, { 5 , 3 , 1 , 4 , 2 }, { 5 , 6 , 7 , 8 , 9 }, { 0 , 6 , 3 , 4 , 12 }, { 9 , 7 , 12 , 4 , 3 }, }; ArrayList<Integer> ans = colMaxSum(mat); System.out.println( "Row " + (ans.get( 0 ) + 1 ) + " has max sum " + ans.get( 1 )); } } // This code is contributed by Vivekkumar Singh |
Python3
# Python3 program to find row with # max sum in a matrix import sys N = 5 # No of rows and column # Function to find the row with max sum def colMaxSum(mat): # Variable to store index of row # with maximum idx = - 1 # Variable to store max sum maxSum = - sys.maxsize # Traverse matrix row wise for i in range ( 0 , N): sum = 0 # calculate sum of row for j in range ( 0 , N): sum + = mat[i][j] # Update maxSum if it is less than # current sum if ( sum > maxSum): maxSum = sum # store index idx = i res = [idx, maxSum] # return result return res # Driver code mat = [[ 1 , 2 , 3 , 4 , 5 ], [ 5 , 3 , 1 , 4 , 2 ], [ 5 , 6 , 7 , 8 , 9 ], [ 0 , 6 , 3 , 4 , 12 ], [ 9 , 7 , 12 , 4 , 3 ]] ans = colMaxSum(mat) print ( "Row" , ans[ 0 ] + 1 , "has max sum" , ans[ 1 ]) # This code is contributed by Sanjit_Prasad |
C#
// C# program to find row with // max sum in a matrix using System; using System.Collections.Generic; public class MaxSum { public static int N; static List< int > colMaxSum( int [, ] mat) { // Variable to store index of row // with maximum int idx = -1; // Variable to store maximum sum int maxSum = int .MinValue; // Traverse the matrix row wise for ( int i = 0; i < N; i++) { int sum = 0; for ( int j = 0; j < N; j++) { sum += mat[i, j]; } // Update maxSum if it is less than // current row sum if (maxSum < sum) { maxSum = sum; // store index idx = i; } } // Arraylist to store values of index // of maximum sum and the maximum sum together List< int > res = new List< int >(); res.Add(idx); res.Add(maxSum); return res; } // Driver code public static void Main(String[] args) { N = 5; int [, ] mat = { { 1, 2, 3, 4, 5 }, { 5, 3, 1, 4, 2 }, { 5, 6, 7, 8, 9 }, { 0, 6, 3, 4, 12 }, { 9, 7, 12, 4, 3 }, }; List< int > ans = colMaxSum(mat); Console.WriteLine( "Row " + (ans[0] + 1) + " has max sum " + ans[1]); } } // This code has been contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to find row with // max sum in a matrix var N; function colMaxSum(mat) { // Variable to store index of row // with maximum var idx = -1; // Variable to store maximum sum var maxSum = -1000000000; // Traverse the matrix row wise for ( var i = 0; i < N; i++) { var sum = 0; for ( var j = 0; j < N; j++) { sum += mat[i][j]; } // Update maxSum if it is less than // current row sum if (maxSum < sum) { maxSum = sum; // store index idx = i; } } // Arraylist to store values of index // of maximum sum and the maximum sum together var res = []; res.push(idx); res.push(maxSum); return res; } // Driver code N = 5; var mat = [ [ 1, 2, 3, 4, 5 ], [ 5, 3, 1, 4, 2 ], [ 5, 6, 7, 8, 9 ], [ 0, 6, 3, 4, 12], [ 9, 7, 12, 4, 3]]; var ans = colMaxSum(mat); document.write( "Row " + (ans[0]+1)+ " has max sum " + ans[1]); </script> |
Row 3 has max sum 35
Time complexity: O(N2)
Auxiliary space: O(1)
Example in c:
Approach:
Initialize a variable max_sum to zero and a variable max_row to -1.
Traverse the matrix row by row:
a. Initialize a variable row_sum to zero.
b. Traverse the elements of the current row and add them to row_sum.
c. If row_sum is greater than max_sum, update max_sum to row_sum and max_row to the current row.
Return max_row.
C
#include <stdio.h> int main() { int mat[3][4] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } }; int m = 3; int n = 4; int max_sum = 0; int max_row = -1; // Traverse the matrix row by row and find the row with // maximum sum for ( int i = 0; i < m; i++) { int row_sum = 0; for ( int j = 0; j < n; j++) { row_sum += mat[i][j]; } if (row_sum > max_sum) { max_sum = row_sum; max_row = i; } } printf ( "Row with maximum sum is: %d\n" , max_row); return 0; } |
C++
#include <iostream> using namespace std; int main() { int mat[3][4] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } }; int m = 3; int n = 4; int max_sum = 0; int max_row = -1; // Traverse the matrix row by row and find the row with // maximum sum for ( int i = 0; i < m; i++) { int row_sum = 0; for ( int j = 0; j < n; j++) { row_sum += mat[i][j]; } if (row_sum > max_sum) { max_sum = row_sum; max_row = i; } } cout << "Row with maximum sum is: " << max_row << endl; return 0; } |
Java
class Main { public static void main(String[] args) { int [][] mat = { { 1 , 2 , 3 , 4 }, { 5 , 6 , 7 , 8 }, { 9 , 10 , 11 , 12 } }; int m = 3 ; int n = 4 ; int max_sum = 0 ; int max_row = - 1 ; // Traverse the matrix row by row and find the row // with maximum sum for ( int i = 0 ; i < m; i++) { int row_sum = 0 ; for ( int j = 0 ; j < n; j++) { row_sum += mat[i][j]; } if (row_sum > max_sum) { max_sum = row_sum; max_row = i; } } System.out.println( "Row with maximum sum is: " + max_row); } } |
Python3
# Create a 3x4 matrix mat = [[ 1 , 2 , 3 , 4 ], [ 5 , 6 , 7 , 8 ], [ 9 , 10 , 11 , 12 ]] m = 3 n = 4 # Initialize max_sum and max_row to 0 max_sum = 0 max_row = - 1 # Traverse the matrix row by row and find the row with maximum sum for i in range (m): row_sum = 0 for j in range (n): row_sum + = mat[i][j] if row_sum > max_sum: max_sum = row_sum max_row = i # Print the index of the row with maximum sum print ( "Row with maximum sum is: " , max_row) |
Javascript
// Create a 3x4 matrix let mat = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]; let m = 3; let n = 4; // Initialize max_sum and max_row to 0 let max_sum = 0; let max_row = -1; // Traverse the matrix row by row and find the row with maximum sum for (let i = 0; i < m; i++) { let row_sum = 0; for (let j = 0; j < n; j++) { row_sum += mat[i][j]; } if (row_sum > max_sum) { max_sum = row_sum; max_row = i; } } // Print the index of the row with maximum sum console.log( "Row with maximum sum is: " , max_row); |
C#
using System; class GFG { public static void Main( string [] args) { int [][] mat = new int [][] { new int [] { 1, 2, 3, 4 }, new int [] { 5, 6, 7, 8 }, new int [] { 9, 10, 11, 12 } }; int m = 3; int n = 4; // Initialize max_sum and max_row to 0 int max_sum = 0; int max_row = -1; // Traverse the matrix row by row and find the row // with maximum sum for ( int i = 0; i < m; i++) { int row_sum = 0; for ( int j = 0; j < n; j++) { row_sum += mat[i][j]; } if (row_sum > max_sum) { max_sum = row_sum; max_row = i; } } // Print the index of the row with maximum sum Console.WriteLine( "Row with maximum sum is: " + max_row); } } |
Row with maximum sum is: 2
time complexity of O(mn)
space complexity of O(n)