Given a matrix mat[][] of dimensionM*N, the task is to find the total maximum possible value must be increased to each cell(say mat[i][j]) such that maximum element of row i and column j remains unchanged.
Examples:
Input: N = 3, M = 3, mat[][] = { {4, 1, 3}, {3, 1, 1}, {2, 2, 0} }
Output: 6
Explanation:
The given matrix is:
4 1 3
3 1 1
2 2 0
Row-wise maximum values are: {4, 3, 2}
Column-wise maximum values are: {4, 2, 3}
After increasing the elements without affecting the row-wise and column-wise maximum values:
4 2 3
3 2 3
2 2 2
The total increase in corresponding cells of the two matrix is ((0 + 1 + 0) + (0 + 1 + 2) + (0 + 0 + 2)) = 6.Input: M = 4, N = 4, mat[][] = { {3, 0, 8, 4}, {2, 4, 5, 7}, {9, 2, 6, 3}, {0, 3, 1, 0} }
Output: 35
Explanation:
The given matrix is:
3 0 8 4
2 4 5 7
9 2 6 3
0 3 1 0
Row-wise maximum values are: {8, 7, 9, 3}
Column-wise maximum values are: {9, 4, 8, 7}
After increasing the elements without affecting the row-wise and column-wise maximum values:
8 4 8 7
7 4 7 7
9 4 8 7
3 3 3 3
The total increase in corresponding cells of the two matrix is ((5 + 4 + 0 + 3) + (5 + 0 + 2 + 0) + (0 + 2 + 2 + 4) + (3 + 0 + 2 + 3)) = 35.
Approach:
- Traverse along each row and column of the given matrix to store the maximum values for each row and column.
- Traverse the given matrix mat[][] and for each cell(say mat[i][j]) and add the difference between the current element and the minimum value of the maximum values along its corresponding row and column as:
difference = min(row[i], cols[j]) – mat[i][j]
- The total values added in the above operations is the required result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum increment// in each cell of the given matrix such// that maximum and minimum value remains// unaffectedint maxIncrease(vector<vector<int> >& matrix){ // Get the row of matrix as M int M = matrix.size(); // Get the column of matrix as N int N = matrix[0].size(); // To store the row-wise // maximum values vector<int> maxRowVal(M, 0); // To store the column-wise // maximum values vector<int> maxColVal(N, 0); // Traverse along the matrix // to store the maximum values // of each row and column for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { // Store the row-wise // maximum values maxRowVal[i] = max(maxRowVal[i], matrix[i][j]); // Store the column-wise // maximum values maxColVal[j] = max(maxColVal[j], matrix[i][j]); } } // Calculate the total amount // of increment int totalIncrease = 0; // Traverse matrix mat[][] for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { // The maximum possible // amount to increase int needToIncrease = min(maxRowVal[i], maxColVal[j]) - matrix[i][j]; // Total increased value totalIncrease += needToIncrease; } } // Return the total // increased value return totalIncrease;}// Driver Codeint main(){ // Given matrix vector<vector<int> > matrix{ { 3, 0, 8, 4 }, { 2, 4, 5, 7 }, { 9, 2, 6, 3 }, { 0, 3, 1, 0 } }; // Function Call cout << maxIncrease(matrix) << endl; return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the maximum increment// in each cell of the given matrix such// that maximum and minimum value remains// unaffectedstatic int maxIncrease(int [][] matrix){ // Get the row of matrix as M int M = matrix.length; // Get the column of matrix as N int N = matrix[0].length; // To store the row-wise // maximum values int []maxRowVal = new int[M]; // To store the column-wise // maximum values int []maxColVal = new int[N]; // Traverse along the matrix // to store the maximum values // of each row and column for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { // Store the row-wise // maximum values maxRowVal[i] = Math.max(maxRowVal[i], matrix[i][j]); // Store the column-wise // maximum values maxColVal[j] = Math.max(maxColVal[j], matrix[i][j]); } } // Calculate the total amount // of increment int totalIncrease = 0; // Traverse matrix mat[][] for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { // The maximum possible // amount to increase int needToIncrease = Math.min(maxRowVal[i], maxColVal[j]) - matrix[i][j]; // Total increased value totalIncrease += needToIncrease; } } // Return the total // increased value return totalIncrease;}// Driver Codepublic static void main(String[] args){ // Given matrix int [][] matrix = { { 3, 0, 8, 4 }, { 2, 4, 5, 7 }, { 9, 2, 6, 3 }, { 0, 3, 1, 0 } }; // Function Call System.out.print(maxIncrease(matrix) + "\n");}}// This code is contributed by gauravrajput1 |
Python3
# Python3 program for the above approach# Function to find the maximum increment# in each cell of the given matrix such# that maximum and minimum value remains# unaffecteddef maxIncrease(matrix): # Get the row of matrix as M M = len(matrix) # Get the column of matrix as N N = len(matrix[0]) # To store the row-wise # maximum values maxRowVal = [0] * M # To store the column-wise # maximum values maxColVal = [0] * (N) # Traverse along the matrix # to store the maximum values # of each row and column for i in range(M): for j in range(N): # Store the row-wise # maximum values maxRowVal[i] = max(maxRowVal[i], matrix[i][j]) # Store the column-wise # maximum values maxColVal[j] = max(maxColVal[j], matrix[i][j]) # Calculate the total amount # of increment totalIncrease = 0 # Traverse matrix mat[][] for i in range(M): for j in range(N): # The maximum possible # amount to increase needToIncrease = (min(maxRowVal[i], maxColVal[j]) - matrix[i][j]) # Total increased value totalIncrease += needToIncrease # Return the total # increased value return totalIncrease# Driver Codeif __name__ == '__main__': # Given matrix matrix = [ [ 3, 0, 8, 4 ], [ 2, 4, 5, 7 ], [ 9, 2, 6, 3 ], [ 0, 3, 1, 0 ] ] # Function call print(maxIncrease(matrix))# This code is contributed mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{// Function to find the maximum increment// in each cell of the given matrix such// that maximum and minimum value remains// unaffectedstatic int maxIncrease(int [,] matrix){ // Get the row of matrix as M int M = matrix.GetLength(0); // Get the column of matrix as N int N = matrix.GetLength(1); // To store the row-wise // maximum values int []maxRowVal = new int[M]; // To store the column-wise // maximum values int []maxColVal = new int[N]; // Traverse along the matrix // to store the maximum values // of each row and column for(int i = 0; i < M; i++) { for(int j = 0; j < N; j++) { // Store the row-wise // maximum values maxRowVal[i] = Math.Max(maxRowVal[i], matrix[i, j]); // Store the column-wise // maximum values maxColVal[j] = Math.Max(maxColVal[j], matrix[i, j]); } } // Calculate the total amount // of increment int totalIncrease = 0; // Traverse matrix [,]mat for(int i = 0; i < M; i++) { for(int j = 0; j < N; j++) { // The maximum possible // amount to increase int needToIncrease = Math.Min(maxRowVal[i], maxColVal[j]) - matrix[i, j]; // Total increased value totalIncrease += needToIncrease; } } // Return the total // increased value return totalIncrease;}// Driver Codepublic static void Main(String[] args){ // Given matrix int [,] matrix = { { 3, 0, 8, 4 }, { 2, 4, 5, 7 }, { 9, 2, 6, 3 }, { 0, 3, 1, 0 } }; // Function call Console.Write(maxIncrease(matrix) + "\n");}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program for the above approach// Function to find the maximum increment// in each cell of the given matrix such// that maximum and minimum value remains// unaffectedfunction maxIncrease(matrix){ // Get the row of matrix as M var M = matrix.length; // Get the column of matrix as N var N = matrix[0].length; // To store the row-wise // maximum values var maxRowVal = Array(M).fill(0); // To store the column-wise // maximum values var maxColVal = Array(N).fill(0); // Traverse along the matrix // to store the maximum values // of each row and column for (var i = 0; i < M; i++) { for (var j = 0; j < N; j++) { // Store the row-wise // maximum values maxRowVal[i] = Math.max(maxRowVal[i], matrix[i][j]); // Store the column-wise // maximum values maxColVal[j] = Math.max(maxColVal[j], matrix[i][j]); } } // Calculate the total amount // of increment var totalIncrease = 0; // Traverse matrix mat[][] for (var i = 0; i < M; i++) { for (var j = 0; j < N; j++) { // The maximum possible // amount to increase var needToIncrease = Math.min(maxRowVal[i], maxColVal[j]) - matrix[i][j]; // Total increased value totalIncrease += needToIncrease; } } // Return the total // increased value return totalIncrease;}// Driver Code// Given matrixvar matrix = [ [ 3, 0, 8, 4 ], [ 2, 4, 5, 7 ], [ 9, 2, 6, 3 ], [ 0, 3, 1, 0 ] ]; // Function Calldocument.write( maxIncrease(matrix) + "<br>"); // This code is contributed by noob2000.</script> |
Output:
35
Time Complexity: O(M*N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
