Given an integer matrix mat[][] of dimensions N * M, the task is to print the maximum product of matrix elements in the path from the top-left cell (0, 0) to the bottom-right cell (N – 1, M – 1) of the given matrix. Only possible moves from any cell (i, j) is (i + 1, j) or (i, j + 1). If the maximum product is negative, then print “-1”.
Examples:
Input: mat[][] = [[1, -2, 1], [1, -2, 1], [3, -4, 1]]
Output: 8
Explanation: The path from top left to bottom right with maximum product is (0, 0) ? (1, 0) -> (1, 1) -> (2, 1) -> (2, 2) = 1 * 1 * ( -2 ) * ( -4 ) * ( 1 ) = 8.
Therefore, the maximum positive product is 8.Input: mat[][] = [[-1, -2, -3], [-2, -3, -3], [-3, -3, -2]]
Output: -1
Explanation: It is not possible to get non-negative product in the path from (0, 0) to (2, 2). Therefore, print -1.
Naive Approach: The simplest approach to solve to recursively traverse from the top-left cell and generate all possible paths from top left to the bottom-right cell by moving rightwards and downwards from each cell. Find the product for each path generated and print the maximum among them.
Time Complexity: O(2max(N, M))
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use Dynamic Programming. Follow the steps below to solve the problem:
- Initialize matrices maxPath[][] and minPath[][], to store maximum and minimum product of paths respectively.
- The idea is to also keep track of the maximum negative product obtained so far, because if any negative product is encountered, then the negative product multiplied by maximum negative product can generate maximum positive product.
- To reach index (i, j), as the possible moves allowed are rightward and downward, so the maximum product can be maximum product or minimum product till (i – 1, j)th index or (i, j – 1)th index multiplied by the element at index (i, j).
- After completing the above steps, if the value of maxPath[M – 1][N – 1] is non-negative, then print it as the positive product path. Otherwise, print “-1”.
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 product// from the top left and bottom right// cell of the given matrix grid[][]int maxProductPath(vector<vector<int>> grid){ // Store dimension of grid int n = grid.size(); int m = grid[0].size(); // Stores maximum product path vector<vector<int>> maxPath(n, vector<int>(m, 0)); // Stores minimum product path vector<vector<int>> minPath(n, vector<int>(m, 0)); // Traverse the grid and update // maxPath and minPath array for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // Initialize to inf and -inf int mn = INT_MAX; int mx = INT_MIN; // Base Case if (i == 0 and j == 0) { mx = grid[i][j]; mn = grid[i][j]; } // Calculate for row: if (i > 0) { int tempmx = max((maxPath[i - 1][j] * grid[i][j]), (minPath[i - 1][j] * grid[i][j])); // Update the maximum mx = max(mx, tempmx); int tempmn = min((maxPath[i - 1][j] * grid[i][j]), (minPath[i - 1][j] * grid[i][j])); // Update the minimum mn = min(mn, tempmn); } // Calculate for column: if (j > 0) { int tempmx = max((maxPath[i][j - 1] * grid[i][j]), (minPath[i][j - 1] * grid[i][j])); // Update the maximum mx = max(mx, tempmx); int tempmn = min((maxPath[i][j - 1] * grid[i][j]), (minPath[i][j - 1] * grid[i][j])); // Update the minimum mn = min(mn, tempmn); } // Update maxPath and minPath maxPath[i][j] = mx; minPath[i][j] = mn; } } // If negative product if(maxPath[n - 1][m - 1] < 0) return -1; // Otherwise else return(maxPath[n - 1][m - 1]);}// Driver Codeint main(){ // Given matrix mat[][] vector<vector<int>> mat = {{1, -2, 1}, {1, -2, 1}, {3, -4, 1}}; // Function Call cout<<(maxProductPath(mat));}// This code is contributed by mohit kumar 29 |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to find the maximum product // from the top left and bottom right // cell of the given matrix grid[][] static int maxProductPath(int[][] grid) { // Store dimension of grid int n = grid.length; int m = grid[0].length; // Stores maximum product path int[][] maxPath = new int[n][m]; // Stores minimum product path int[][] minPath = new int[n][m]; // Traverse the grid and update // maxPath and minPath array for(int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // Initialize to inf and -inf int mn = Integer.MAX_VALUE; int mx = Integer.MIN_VALUE; // Base Case if(i == 0 && j == 0) { mx = grid[i][j]; mn = grid[i][j]; } // Calculate for row: if(i > 0) { int tempmx =Math.max((maxPath[i - 1][j] * grid[i][j]),(minPath[i - 1][j] * grid[i][j])); // Update the maximum mx = Math.max(mx, tempmx); int tempmn = Math.min((maxPath[i - 1][j] * grid[i][j]),(minPath[i - 1][j] * grid[i][j])); // Update the minimum mn=Math.min(mn, tempmn); } // Calculate for column if(j > 0) { int tempmx = Math.max((maxPath[i][j - 1] * grid[i][j]),(minPath[i][j - 1] * grid[i][j])); // Update the maximum mx = Math.max(mx, tempmx); int tempmn = Math.min((maxPath[i][j - 1] * grid[i][j]),(minPath[i][j - 1] * grid[i][j])); // Update the minimum mn=Math.min(mn, tempmn); } // Update maxPath and minPath maxPath[i][j] = mx; minPath[i][j] = mn; } } // If negative product if(maxPath[n - 1][m - 1] < 0) { return -1; } // Otherwise else { return(maxPath[n - 1][m - 1]); } } // Driver Code public static void main (String[] args) { // Given matrix mat[][] int[][] mat = {{1, -2, 1}, {1, -2, 1}, {3, -4, 1}}; // Function Call System.out.println(maxProductPath(mat)); }}// This code is contributed by rag2127 |
Python3
# Python program for the above approach# Function to find the maximum product# from the top left and bottom right# cell of the given matrix grid[][]def maxProductPath(grid): # Store dimension of grid n, m = len(grid), len(grid[0]) # Stores maximum product path maxPath = [[0 for i in range(m)] for j in range(n)] # Stores minimum product path minPath = [[0 for i in range(m)] for j in range(n)] # Traverse the grid and update # maxPath and minPath array for i in range(n): for j in range(m): # Initialize to inf and -inf mn = float("inf") mx = float("-inf") # Base Case if (i == 0 and j == 0): mx = grid[i][j] mn = grid[i][j] # Calculate for row: if i > 0: tempmx = max((maxPath[i - 1][j] * grid[i][j]), (minPath[i - 1][j] * grid[i][j])) # Update the maximum mx = max(mx, tempmx) tempmn = min((maxPath[i - 1][j] * grid[i][j]), (minPath[i - 1][j] * grid[i][j])) # Update the minimum mn = min(mn, tempmn) # Calculate for column: if (j > 0): tempmx = max((maxPath[i][j - 1] * grid[i][j]), (minPath[i][j - 1] * grid[i][j])) # Update the maximum mx = max(mx, tempmx) tempmn = min((maxPath[i][j - 1] * grid[i][j]), (minPath[i][j - 1] * grid[i][j])) # Update the minimum mn = min(mn, tempmn) # Update maxPath and minPath maxPath[i][j] = mx minPath[i][j] = mn # If negative product if(maxPath[n - 1][m - 1] < 0): return -1 # Otherwise else: return(maxPath[n - 1][m - 1])# Driver Code# Given matrix mat[][]mat = [[1, -2, 1], [1, -2, 1], [3, -4, 1]]# Function Callprint(maxProductPath(mat)) |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the maximum product // from the top left and bottom right // cell of the given matrix grid[][] static int maxProductPath(int[,] grid) { // Store dimension of grid int n = grid.GetLength(0); int m = grid.GetLength(1); // Stores maximum product path int[,] maxPath = new int[n, m]; // Stores minimum product path int[,] minPath = new int[n, m]; // Traverse the grid and update // maxPath and minPath array for(int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // Initialize to inf and -inf int mn = Int32.MaxValue; int mx = Int32.MinValue; // Base Case if(i == 0 && j == 0) { mx = grid[i, j]; mn = grid[i, j]; } // Calculate for row: if(i > 0) { int tempmx = Math.Max((maxPath[i - 1, j] * grid[i, j]), (minPath[i - 1, j] * grid[i, j])); // Update the maximum mx = Math.Max(mx, tempmx); int tempmn = Math.Min((maxPath[i - 1, j] * grid[i, j]), (minPath[i - 1, j] * grid[i, j])); // Update the minimum mn = Math.Min(mn, tempmn); } // Calculate for column if(j > 0) { int tempmx = Math.Max((maxPath[i, j - 1] * grid[i, j]), (minPath[i, j - 1] * grid[i, j])); // Update the maximum mx = Math.Max(mx, tempmx); int tempmn = Math.Min((maxPath[i, j - 1] * grid[i, j]), (minPath[i, j - 1] * grid[i,j])); // Update the minimum mn = Math.Min(mn, tempmn); } // Update maxPath and minPath maxPath[i,j] = mx; minPath[i,j] = mn; } } // If negative product if(maxPath[n - 1, m - 1] < 0) { return -1; } // Otherwise else { return(maxPath[n - 1, m - 1]); } } // Driver Code static public void Main () { // Given matrix mat[][] int[,] mat={{1, -2, 1}, {1, -2, 1}, {3, -4, 1}}; // Function Call Console.WriteLine(maxProductPath(mat)); }}// This code is contributed by avanitrachhadiya2155 |
Javascript
<script>// JavaScript program for the above approach// Function to find the maximum product// from the top left and bottom right// cell of the given matrix grid[][]function maxProductPath(grid){ // Store dimension of grid var n = grid.length; var m = grid[0].length; // Stores maximum product path var maxPath = Array.from(Array(n), ()=>Array(m).fill(0)); // Stores minimum product path var minPath = Array.from(Array(n), ()=>Array(m).fill(0)); // Traverse the grid and update // maxPath and minPath array for (var i = 0; i < n; i++) { for (var j = 0; j < m; j++) { // Initialize to inf and -inf var mn = 1000000000; var mx = -1000000000; // Base Case if (i == 0 && j == 0) { mx = grid[i][j]; mn = grid[i][j]; } // Calculate for row: if (i > 0) { var tempmx = Math.max((maxPath[i - 1][j] * grid[i][j]), (minPath[i - 1][j] * grid[i][j])); // Update the maximum mx = Math.max(mx, tempmx); var tempmn = Math.min((maxPath[i - 1][j] * grid[i][j]), (minPath[i - 1][j] * grid[i][j])); // Update the minimum mn = Math.min(mn, tempmn); } // Calculate for column: if (j > 0) { var tempmx = Math.max((maxPath[i][j - 1] * grid[i][j]), (minPath[i][j - 1] * grid[i][j])); // Update the maximum mx = Math.max(mx, tempmx); var tempmn = Math.min((maxPath[i][j - 1] * grid[i][j]), (minPath[i][j - 1] * grid[i][j])); // Update the minimum mn = Math.min(mn, tempmn); } // Update maxPath and minPath maxPath[i][j] = mx; minPath[i][j] = mn; } } // If negative product if(maxPath[n - 1][m - 1] < 0) return -1; // Otherwise else return(maxPath[n - 1][m - 1]);}// Driver Code// Given matrix mat[][]var mat = [[1, -2, 1], [1, -2, 1], [3, -4, 1]]; // Function Calldocument.write(maxProductPath(mat));</script> |
Output:
8
Time Complexity: O(M*N)
Auxiliary Space: 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!
