Given a matrix of N X M of positive integers, the task is to find out whether it is possible to make the matrix increasing or not. Print the matrix constructed otherwise print -1. Matrix elements should be greater than zero.
A matrix is said to be increasing matrix if:
- For each row, the elements are in the increasing order.
- For each column, the elements are in the increasing order.
Examples:
Input : N = 4, M = 4
1 2 2 3
1 -1 7 -1
6 -1 -1 -1
-1 -1 -1 -1
Output :
1 2 2 3
1 2 7 7
6 6 7 7
6 6 7 7
As we can see that this is the increasing matrix.Input : N = 2, M = 3
1 4 -1
1 -1 3
Output : -1
Here, in the first row, we have to put something greater than 4 to make it increasing sequence. But, after this, the 3rd column will never be in increasing order. So, it is impossible to make it increasing matrix.
Note: There can be more than one solution for a matrix.
Approach: Let dp[i][j] denote the element at row i and column j of matrix dp. Since the matrix is non-decreasing, the following two conditions should be held:
- dp[i][j] >= dp[i][j-1], in row i elements are non-decreasing.
- dp[i][j] >= dp[i-1][j], in column j elements are non-decreasing.
This implies that dp[i][j] >= dp[r] for every 1 <= r <= i, 1 <= c <= j (one element is greater than all the elements that are up to the left).
Let i be the first row of dp that contains a -1 and in this row let j be the column of the leftmost -1. It is always convenient to replace dp[i][j] with the minimum
possible value, otherwise, it may be impossible to find a valid value for another -1 that is down to the right. So one possible solution (and the lexicographically smallest) is to set dp[i][j] = max { dp[i][j-1], dp[i-1][j] }.
After filling some of the unknown positions in dp, it may turn out that one of the values of dp is smaller than some of the elements that are up to the left. In this case, there is no solution.
Implementation:
C++
// CPP program to Check if we can make // the given matrix increasing matrix or not #include <bits/stdc++.h> using namespace std; #define n 4 #define m 4 // Function to find increasing matrix void findIncreasingMatrix( int dp[n + 1][m + 1]) { bool flag = false ; for ( int i = 1; i <= n; ++i) { for ( int j = 1; j <= m; ++j) { // Putting max into b as per the above approach int b = max(dp[i - 1][j], dp[i][j - 1]); // If b is -1 than putting 1 to it b = max(1, b); // If dp[i][j] has to be filled with max if (dp[i][j] == -1) dp[i][j] = b; // If dp[i][j] is less than from it's left // element or from it's upper element else if (dp[i][j] < b) flag = true ; } } // If it is not possible if (flag) cout << -1 << '\n' ; else { // Printing the increasing matrix for ( int i = 1; i <= n; ++i) { for ( int j = 1; j <= m; ++j) { cout << dp[i][j] << ' ' ; } cout << endl; } } } // Drivers code int main() { /* Here the matrix is 1 2 3 3 1 -1 7 -1 6 -1 -1 -1 -1 -1 -1 -1 Putting 0 in first row & column */ int dp[n + 1][m + 1] = { { 0, 0, 0, 0, 0 }, { 0, 1, 2, 2, 3 }, { 0, 1, -1, 7, -1 }, { 0, 6, -1, -1, -1 }, { 0, -1, -1, -1, -1 } }; findIncreasingMatrix(dp); } |
Java
// Java program to Check if we // can make the given matrix // increasing matrix or not import java.util.*; import java.lang.*; import java.io.*; class GFG { static final int n = 4 ; static final int m = 4 ; // Function to find increasing matrix static void findIncreasingMatrix( int dp[][]) { boolean flag = false ; for ( int i = 1 ; i <= n; ++i) { for ( int j = 1 ; j <= m; ++j) { // Putting max into b as per // the above approach int b = Math.max(dp[i - 1 ][j], dp[i][j - 1 ]); // If b is -1 than putting 1 to it b = Math.max( 1 , b); // If dp[i][j] has to be // filled with max if (dp[i][j] == - 1 ) dp[i][j] = b; // If dp[i][j] is less than from // it's left element or from // it's upper element else if (dp[i][j] < b) flag = true ; } } // If it is not possible if (flag == true ) System.out.println( "-1" ); else { // Printing the increasing matrix for ( int i = 1 ; i <= n; ++i) { for ( int j = 1 ; j <= m; ++j) { System.out.print(dp[i][j] + " " ); } System.out.println(); } } } // Driver code public static void main(String args[]) { /* Here the matrix is 1 2 3 3 1 -1 7 -1 6 -1 -1 -1 -1 -1 -1 -1 Putting 0 in first row & column */ int dp[][] = {{ 0 , 0 , 0 , 0 , 0 }, { 0 , 1 , 2 , 2 , 3 }, { 0 , 1 , - 1 , 7 , - 1 }, { 0 , 6 , - 1 , - 1 , - 1 }, { 0 , - 1 , - 1 , - 1 , - 1 }}; findIncreasingMatrix(dp); } } // This code is contributed // by Subhadeep |
Python3
# Python3 program to Check if we can make # the given matrix increasing matrix or not # Function to find increasing matrix def findIncreasingMatrix(dp): flag = False for i in range ( 1 , n + 1 ): for j in range ( 1 , m + 1 ): # Putting max into b as per # the above approach b = max (dp[i - 1 ][j], dp[i][j - 1 ]) # If b is -1 than putting 1 to it b = max ( 1 , b) # If dp[i][j] has to be filled with max if dp[i][j] = = - 1 : dp[i][j] = b # If dp[i][j] is less than from it's left # element or from it's upper element elif dp[i][j] < b: flag = True # If it is not possible if flag: print ( - 1 ) else : # Printing the increasing matrix for i in range ( 1 , n + 1 ): for j in range ( 1 , m + 1 ): print (dp[i][j], end = ' ' ) print () # Driver code if __name__ = = "__main__" : dp = [[ 0 , 0 , 0 , 0 , 0 ], [ 0 , 1 , 2 , 2 , 3 ], [ 0 , 1 , - 1 , 7 , - 1 ], [ 0 , 6 , - 1 , - 1 , - 1 ], [ 0 , - 1 , - 1 , - 1 , - 1 ]] n = m = 4 findIncreasingMatrix(dp) # This code is contributed # by Rituraj Jain |
C#
// C# program to Check if we // can make the given matrix // increasing matrix or not using System; class GFG { static readonly int n = 4; static readonly int m = 4; // Function to find increasing matrix static void findIncreasingMatrix( int [,]dp) { bool flag = false ; for ( int i = 1; i <= n; ++i) { for ( int j = 1; j <= m; ++j) { // Putting max into b as per // the above approach int b = Math.Max(dp[i - 1, j], dp[i, j - 1]); // If b is -1 than putting 1 to it b = Math.Max(1, b); // If dp[i,j] has to be // filled with max if (dp[i, j] == -1) dp[i, j] = b; // If dp[i,j] is less than from // it's left element or from // it's upper element else if (dp[i, j] < b) flag = true ; } } // If it is not possible if (flag == true ) Console.WriteLine( "-1" ); else { // Printing the increasing matrix for ( int i = 1; i <= n; ++i) { for ( int j = 1; j <= m; ++j) { Console.Write(dp[i, j] + " " ); } Console.WriteLine(); } } } // Driver code public static void Main() { /* Here the matrix is 1 2 3 3 1 -1 7 -1 6 -1 -1 -1 -1 -1 -1 -1 Putting 0 in first row & column */ int [,]dp = {{ 0, 0, 0, 0, 0 }, { 0, 1, 2, 2, 3 }, { 0, 1, -1, 7, -1 }, { 0, 6, -1, -1, -1 }, { 0, -1, -1, -1, -1 }}; findIncreasingMatrix(dp); } } /* This code contributed by PrinciRaj1992 */ |
PHP
<?php // PHP program to Check if we can make // the given matrix increasing matrix or not $n = 4; $m = 4; // Function to find increasing matrix function findIncreasingMatrix( $dp ) { global $n ; global $m ; $flag = false; for ( $i = 1; $i <= $n ; ++ $i ) { for ( $j = 1; $j <= $m ; ++ $j ) { // Putting max into b as per the above approach $b = max( $dp [ $i - 1][ $j ], $dp [ $i ][ $j - 1]); // If b is -1 than putting 1 to it $b = max(1, $b ); // If dp[i][j] has to be filled with max if ( $dp [ $i ][ $j ] == -1) $dp [ $i ][ $j ] = $b ; // If dp[i][j] is less than from it's left // element or from it's upper element else if ( $dp [ $i ][ $j ] < $b ) $flag = true; } } // If it is not possible if ( $flag ) echo -1, '\n' ; else { // Printing the increasing matrix for ( $i = 1; $i <= $n ; ++ $i ) { for ( $j = 1; $j <= $m ; ++ $j ) { echo $dp [ $i ][ $j ], ' ' ; } echo "\n" ; } } } // Driver Code /* Here the matrix is 1 2 3 3 1 -1 7 -1 6 -1 -1 -1 -1 -1 -1 -1 Putting 0 in first row & column */ $dp = array ( array (0, 0, 0, 0, 0), array (0, 1, 2, 2, 3), array (0, 1, -1, 7, -1), array (0, 6, -1, -1, -1), array (0, -1, -1, -1, -1)); findIncreasingMatrix( $dp ); // This code is contributed by akt_mit ?> |
Javascript
<script> // Javascript program to Check if we can make // the given matrix increasing matrix or not let n = 4; let m = 4; // Function to find increasing matrix function findIncreasingMatrix(dp) { let flag = false ; for (let i = 1; i <= n; ++i) { for (let j = 1; j <= m; ++j) { // Putting max into b as per the above approach let b = Math.max(dp[i - 1][j], dp[i][j - 1]); // If b is -1 than putting 1 to it b = Math.max(1, b); // If dp[i][j] has to be filled with max if (dp[i][j] == -1) dp[i][j] = b; // If dp[i][j] is less than from it's left // element or from it's upper element else if (dp[i][j] < b) flag = true ; } } // If it is not possible if (flag) document.write(-1 + "</br>" ); else { // Printing the increasing matrix for (let i = 1; i <= n; ++i) { for (let j = 1; j <= m; ++j) { document.write(dp[i][j] + " " ); } document.write( "</br>" ); } } } /* Here the matrix is 1 2 3 3 1 -1 7 -1 6 -1 -1 -1 -1 -1 -1 -1 Putting 0 in first row & column */ let dp = [ [ 0, 0, 0, 0, 0 ], [ 0, 1, 2, 2, 3 ], [ 0, 1, -1, 7, -1 ], [ 0, 6, -1, -1, -1 ], [ 0, -1, -1, -1, -1 ] ]; findIncreasingMatrix(dp); // This code is contributed by divyesh072019. </script> |
1 2 2 3 1 2 7 7 6 6 7 7 6 6 7 7
Complexity Analysis:
- Time complexity: O(m*n) where m and n are columns and rows of given matrix
- Auxiliary Space: O(m*n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!