Given a matrix mat[][] of dimension N*M which is sorted row-wise and column-wise, the task is to find the sum of the elements of the matrix by replacing all 0s in the matrix with any value such that the matrix remains sorted row-wise and column-wise. If it is not possible, then print “-1”.
Note: 0s will be only present in internal cells. i.e., neither in the first row or column nor in the last row or column.
Examples:
Input: mat[][] = {{3, 4, 5, 6}, {4, 0, 7, 8}, {6, 8, 0, 10}, {7, 9, 10, 12}}
Output: 116
Explanation:
The new matrix formed after replacing zeroes is:
[[3, 4, 5, 6],
[4, 7, 7, 8],
[6, 8, 10, 10],
[7, 9, 10, 12]]
which is sorted and has a maximum sum i.e. 116Input: mat[][] = {{1, 2, 4}, {2, 0, 5}, {5, 6, 7}}
Output: 37
Approach: To make the matrix sorted and also to maximize the sums, the zeroes can be replaced by a number that is smaller than or equal to the next element in its row or column. Since the value of zero to be changed depends on the value of its next row and column, the replacement should be done from the end of the matrix. Therefore, traverse the matrix from the end and replace the cells where mat[i][j] is zero with min(mat[i][j + 1], mat[i + 1][j]) and also check the new matrix is sorted or not.
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 sum of// the given matrix after replacing 0s// with any elementint findMaximumSum(int* mat, int n, int m){ // Traverse the given matrix from // the end for (int i = n - 2; i > 0; i--) { for (int j = m - 2; j > 0; j--) { // If the element is 0 if (mat[i * m + j] == 0) { // Replace the 0s mat[i * m + j] = min(mat[i * m + (j + 1)], mat[(i + 1) * m + j]); } } } // Stores the sum of matrix elements int sum = 0; // Traverse the matrix mat[][] for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // Updating the sum sum += mat[i * m + j]; // Checking if not sorted if ((i + 1 < n && mat[i * m + j] > mat[(i + 1) * m + j]) || (j + 1 < m && mat[i * m + j] > mat[i * m + (j + 1)])) { return -1; } } } // Return the maximum value of the sum return sum;}// Driver Codeint main(){ int N = 3, M = 3; int mat[N][M] = { { 1, 2, 4 }, { 2, 0, 5 }, { 5, 6, 7 } }; cout << findMaximumSum((int*)mat, N, M); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Driver Code public static void main(String[] args) { int[][] mat = { { 1, 2, 4 }, { 2, 0, 5 }, { 5, 6, 7 } }; System.out.println(findMaximumSum(mat)); } // Function to find the maximum sum of // the given matrix after replacing 0s // with any element public static int findMaximumSum(int[][] mat) { int N = mat.length; int M = mat[0].length; // Traverse the given matrix from // the end for (int i = N - 2; i > 0; i--) { for (int j = M - 2; j > 0; j--) { // If the element is 0 if (mat[i][j] == 0) { // Replace the 0's mat[i][j] = Math.min(mat[i][j + 1], mat[i + 1][j]); } } } // Stores the sum of matrix elements int sum = 0; // Traverse the matrix mat[][] for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { // Updating the sum sum += mat[i][j]; // Checking if not sorted if ((i + 1 < N && mat[i][j] > mat[i + 1][j]) || (j + 1 < M && mat[i][j] > mat[i][j + 1])) return -1; } } // Return the maximum value of the sum return sum; }}// This code is contributed by Kdheeraj. |
Python3
# python program for the above approach# Function to find the maximum sum of# the given matrix after replacing 0s# with any elementdef findMaximumSum(mat, n, m): # Traverse the given matrix from # the end for i in range(n-2, 0, -1): for j in range(m-2, 0, -1): # If the element is 0 if (mat[i][j] == 0): # Replace the 0s mat[i][j] = min(mat[i][(j + 1)], mat[(i + 1)][j]) # Stores the sum of matrix elements sum = 0 # Traverse the matrix mat[][] for i in range(0, n): for j in range(0, m): # Updating the sum sum += mat[i][j] # Checking if not sorted if ((i + 1 < n and mat[i][j] > mat[(i + 1)][j]) or (j + 1 < m and mat[i][j] > mat[i][(j + 1)])): return -1 # Return the maximum value of the sum return sum# driver codeN = 3M = 3mat = [[1, 2, 4], [2, 0, 5], [5, 6, 7]]print(findMaximumSum(mat, N, M))# This code is contributed by amreshkumar3 |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the maximum sum of // the given matrix after replacing 0s // with any element static int findMaximumSum(int[, ] mat, int n, int m) { // Traverse the given matrix from // the end for (int i = n - 2; i > 0; i--) { for (int j = m - 2; j > 0; j--) { // If the element is 0 if (mat[i, j] == 0) { // Replace the 0s mat[i, j] = Math.Min(mat[i, (j + 1)], mat[(i + 1), j]); } } } // Stores the sum of matrix elements int sum = 0; // Traverse the matrix mat[][] for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // Updating the sum sum += mat[i, j]; // Checking if not sorted if ((i + 1 < n && mat[i, j] > mat[(i + 1), j]) || (j + 1 < m && mat[i, j] > mat[i, (j + 1)])) { return -1; } } } // Return the maximum value of the sum return sum; } // Driver Code public static void Main() { int N = 3, M = 3; int[, ] mat = { { 1, 2, 4 }, { 2, 0, 5 }, { 5, 6, 7 } }; Console.WriteLine(findMaximumSum(mat, N, M)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the maximum sum of // the given matrix after replacing 0s // with any element function findMaximumSum(mat, n, m) { // Traverse the given matrix from // the end for (let i = n - 2; i > 0; i--) { for (let j = m - 2; j > 0; j--) { // If the element is 0 if (mat[i][j] == 0) { // Replace the 0s mat[i][j] = Math.min(mat[i][j + 1], mat[i + 1][j]); } } } // Stores the sum of matrix elements let sum = 0; // Traverse the matrix mat[][] for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { // Updating the sum sum += mat[i][j]; // Checking if not sorted if ((i + 1 < n && mat[i][j] > mat[i + 1][j]) || (j + 1 < m && mat[i][j] > mat[i][(j + 1)])) { return -1; } } } // Return the maximum value of the sum return sum; } // Driver Code let N = 3, M = 3; let mat = [[1, 2, 4], [2, 0, 5], [5, 6, 7]]; document.write(findMaximumSum(mat, N, M)); // This code is contributed by Potta Lokesh </script> |
37
Time Complexity: O(N*M)
Auxiliary Space: O(1)
