Given a gold mine represented as a 2d matrix mat[][], where each cell contains a positive integer indicating the amount of gold (in tons) available in that field. The miner can start from any row in the first column. From any cell, the miner is allowed to move in one of the following three directions:
- Diagonally up-right.
- Directly right.
- Diagonally down-right.
The miner continues moving in this way until reaching the last column or until no further move is possible. Find the maximum amount of gold the miner can collect following these rules.
Examples:
Input: mat[][] = [[1, 3, 3],
[2, 1, 4],
[0, 6, 4]]
Output: 12
Explanation: The miner starts from the second row of the first column (collecting 2 tons of gold), moves to the third row of the second column (collecting 6 tons of gold), and then to the second row of the third column (collecting 4 tons of gold), for a total of 2 + 6 + 4 = 12 tons of gold collected.
Input: mat[][] = [[1, 3, 1, 5],
[2, 2, 4, 1],
[5, 0, 2, 3],
[0, 6, 1, 2]];
Output: 16
Explanation: The miner starts from the third row of the first column (collecting 5 tons of gold), moves to the second row of the second column (collecting 2 tons), then to the second row of the third column (collecting 4 tons), and finally to the first row of the fourth column (collecting 5 tons), for a total of 5 + 2 + 4 + 5 = 16 tons of gold collected.
[Naive Approach] Recursive DFS
The idea is to try all possible paths starting from each cell in the first column using recursion.
From each cell (x, y), we recursively call three directions: collectGold(x-1, y+1) -> right upper , collectGold(x, y+1) -> right , and collectGold(x+1, y+1) -> right lower, to explore all valid moves and take the maximum.
C++
#include <iostream>
#include <vector>
using namespace std;
int collectGold(int x, int y, vector<vector<int>> &mat) {
int n = mat.size(), m = mat[0].size();
// base case
if (x < 0 || x >= n || y >= m) {
return 0;
}
// move to the right-upper cell
int rightUpper = collectGold(x - 1, y + 1, mat);
// move directly to the right
int right = collectGold(x, y + 1, mat);
// move to the right-lower cell
int rightLower = collectGold(x + 1, y + 1, mat);
// return the max gold collected from the three options
return mat[x][y] + max(max(rightUpper, right), rightLower);
}
int maxGold(vector<vector<int>> &mat) {
int n = mat.size(), m = mat[0].size();
int result = 0;
// try starting from each row in the first column
for (int i = 0; i < n; i++) {
int gold = collectGold(i, 0, mat);
result = max(result, gold);
}
return result;
}
int main() {
vector<vector<int>> mat = {
{1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2}
};
cout << maxGold(mat) << endl;
return 0;
}
class GfG {
static int collectGold(int x, int y, int[][] mat) {
int n = mat.length, m = mat[0].length;
// base case
if (x < 0 || x >= n || y >= m) {
return 0;
}
// move to the right-upper cell
int rightUpper = collectGold(x - 1, y + 1, mat);
// move directly to the right
int right = collectGold(x, y + 1, mat);
// move to the right-lower cell
int rightLower = collectGold(x + 1, y + 1, mat);
// return the max gold collected from the three options
return mat[x][y] + Math.max(Math.max(rightUpper, right), rightLower);
}
static int maxGold(int[][] mat) {
int n = mat.length, m = mat[0].length;
int result = 0;
// try starting from each row in the first column
for (int i = 0; i < n; i++) {
int gold = collectGold(i, 0, mat);
result = Math.max(result, gold);
}
return result;
}
public static void main(String[] args) {
int[][] mat = {
{1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2}
};
System.out.println(maxGold(mat));
}
}
def collectGold(x, y, mat):
n = len(mat)
m = len(mat[0])
# base case
if x < 0 or x >= n or y >= m:
return 0
# move to the right-upper cell
rightUpper = collectGold(x - 1, y + 1, mat)
# move directly to the right
right = collectGold(x, y + 1, mat)
# move to the right-lower cell
rightLower = collectGold(x + 1, y + 1, mat)
# return the max gold collected from the three options
return mat[x][y] + max(rightUpper, right, rightLower)
def maxGold(mat):
n = len(mat)
m = len(mat[0])
result = 0
# try starting from each row in the first column
for i in range(n):
gold = collectGold(i, 0, mat)
result = max(result, gold)
return result
if __name__ == "__main__":
mat = [
[1, 3, 1, 5],
[2, 2, 4, 1],
[5, 0, 2, 3],
[0, 6, 1, 2]
]
print(maxGold(mat))
using System;
class GfG {
static int collectGold(int x, int y, int[][] mat) {
int n = mat.Length, m = mat[0].Length;
// base case
if (x < 0 || x >= n || y >= m) {
return 0;
}
// move to the right-upper cell
int rightUpper = collectGold(x - 1, y + 1, mat);
// move directly to the right
int right = collectGold(x, y + 1, mat);
// move to the right-lower cell
int rightLower = collectGold(x + 1, y + 1, mat);
// return the max gold collected from the three options
return mat[x][y] + Math.Max(Math.Max(rightUpper, right), rightLower);
}
static int maxGold(int[][] mat) {
int n = mat.Length, m = mat[0].Length;
int result = 0;
// try starting from each row in the first column
for (int i = 0; i < n; i++) {
int gold = collectGold(i, 0, mat);
result = Math.Max(result, gold);
}
return result;
}
static void Main() {
int[][] mat = new int[][] {
new int[] {1, 3, 1, 5},
new int[] {2, 2, 4, 1},
new int[] {5, 0, 2, 3},
new int[] {0, 6, 1, 2}
};
Console.WriteLine(maxGold(mat));
}
}
function collectGold(x, y, mat) {
let n = mat.length, m = mat[0].length;
// base case
if (x < 0 || x >= n || y >= m) {
return 0;
}
// move to the right-upper cell
let rightUpper = collectGold(x - 1, y + 1, mat);
// move directly to the right
let right = collectGold(x, y + 1, mat);
// move to the right-lower cell
let rightLower = collectGold(x + 1, y + 1, mat);
// return the max gold collected from the three options
return mat[x][y] + Math.max(rightUpper, right, rightLower);
}
function maxGold(mat) {
let n = mat.length, m = mat[0].length;
let result = 0;
// try starting from each row in the first column
for (let i = 0; i < n; i++) {
let gold = collectGold(i, 0, mat);
result = Math.max(result, gold);
}
return result;
}
// Driver Code
let mat = [
[1, 3, 1, 5],
[2, 2, 4, 1],
[5, 0, 2, 3],
[0, 6, 1, 2]
];
console.log(maxGold(mat));
Time Complexity: O(3^(n * m)), from each cell, 3 recursive calls are made, leading to exponential growth.
Auxiliary Space: O(n × m) due to recursion stack in the worst case (depth can go up to m steps, each from different rows).
[Better approach 1] Top-Down Dynamic Programming (Memoization) - O(n×m) Time and O(n×m) Space
The idea is to start from each cell in the first column and explore all valid paths using dfs.
At each step (x, y), we try three moves: collectGold(x-1, y+1) -> right upper , collectGold(x, y+1) -> right , and collectGold(x+1, y+1) -> right lower.
We store results in a memo table to avoid recalculating overlapping subproblems.
C++
#include <iostream>
#include <vector>
using namespace std;
int collectGold(int x, int y, vector<vector<int>> &mat,
vector<vector<int>> &memo) {
int n = mat.size(), m = mat[0].size();
// base case
if (x < 0 || x >= n || y >= m) {
return 0;
}
// return already computed value
if (memo[x][y] != -1) {
return memo[x][y];
}
// move to the right-upper cell
int rightUpper = collectGold(x - 1, y + 1, mat, memo);
// move directly to the right
int right = collectGold(x, y + 1, mat, memo);
// move to the right-lower cell
int rightLower = collectGold(x + 1, y + 1, mat, memo);
// store and return the max gold
// collected from the three options
return memo[x][y] = mat[x][y] +
max(max(rightUpper, right), rightLower);
}
int maxGold(vector<vector<int>> &mat) {
int n = mat.size(), m = mat[0].size();
int result = 0;
// initialize memo with -1
vector<vector<int>> memo(n, vector<int>(m, -1));
// try starting from each row in the first column
for (int i = 0; i < n; i++) {
int gold = collectGold(i, 0, mat, memo);
result = max(result, gold);
}
return result;
}
int main() {
vector<vector<int>> mat = {
{1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2}
};
cout << maxGold(mat) << endl;
return 0;
}
import java.util.Arrays;
class GfG {
static int collectGold(int x, int y, int[][] mat, int[][] memo) {
int n = mat.length, m = mat[0].length;
// base case
if (x < 0 || x >= n || y >= m) {
return 0;
}
// return already computed value
if (memo[x][y] != -1) {
return memo[x][y];
}
// move to the right-upper cell
int rightUpper = collectGold(x - 1, y + 1, mat, memo);
// move directly to the right
int right = collectGold(x, y + 1, mat, memo);
// move to the right-lower cell
int rightLower = collectGold(x + 1, y + 1, mat, memo);
// store and return the max gold
// collected from the three options
return memo[x][y] = mat[x][y] +
Math.max(Math.max(rightUpper, right), rightLower);
}
static int maxGold(int[][] mat) {
int n = mat.length, m = mat[0].length;
int result = 0;
// initialize memo with -1
int[][] memo = new int[n][m];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
// try starting from each row in the first column
for (int i = 0; i < n; i++) {
int gold = collectGold(i, 0, mat, memo);
result = Math.max(result, gold);
}
return result;
}
public static void main(String[] args) {
int[][] mat = {
{1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2}
};
System.out.println(maxGold(mat));
}
}
def collectGold(x, y, mat, memo):
n = len(mat)
m = len(mat[0])
# base case
if x < 0 or x >= n or y >= m:
return 0
# return already computed value
if memo[x][y] != -1:
return memo[x][y]
# move to the right-upper cell
rightUpper = collectGold(x - 1, y + 1, mat, memo)
# move directly to the right
right = collectGold(x, y + 1, mat, memo)
# move to the right-lower cell
rightLower = collectGold(x + 1, y + 1, mat, memo)
# store and return the max gold
# collected from the three options
memo[x][y] = mat[x][y] + max(rightUpper, right, rightLower)
return memo[x][y]
def maxGold(mat):
n = len(mat)
m = len(mat[0])
result = 0
# initialize memo with -1
memo = [[-1 for _ in range(m)] for _ in range(n)]
# try starting from each row in the first column
for i in range(n):
gold = collectGold(i, 0, mat, memo)
result = max(result, gold)
return result
if __name__ == "__main__":
mat = [
[1, 3, 1, 5],
[2, 2, 4, 1],
[5, 0, 2, 3],
[0, 6, 1, 2]
]
print(maxGold(mat))
using System;
class GfG {
static int collectGold(int x, int y, int[][] mat, int[][] memo) {
int n = mat.Length, m = mat[0].Length;
// base case
if (x < 0 || x >= n || y >= m) {
return 0;
}
// return already computed value
if (memo[x][y] != -1) {
return memo[x][y];
}
// move to the right-upper cell
int rightUpper = collectGold(x - 1, y + 1, mat, memo);
// move directly to the right
int right = collectGold(x, y + 1, mat, memo);
// move to the right-lower cell
int rightLower = collectGold(x + 1, y + 1, mat, memo);
// store and return the max gold collected from the three options
return memo[x][y] = mat[x][y] +
Math.Max(Math.Max(rightUpper, right), rightLower);
}
static int maxGold(int[][] mat) {
int n = mat.Length, m = mat[0].Length;
int result = 0;
// initialize memo with -1
int[][] memo = new int[n][];
for (int i = 0; i < n; i++) {
memo[i] = new int[m];
for (int j = 0; j < m; j++) {
memo[i][j] = -1;
}
}
// try starting from each row in the first column
for (int i = 0; i < n; i++) {
int gold = collectGold(i, 0, mat, memo);
result = Math.Max(result, gold);
}
return result;
}
static void Main() {
int[][] mat = new int[][] {
new int[] {1, 3, 1, 5},
new int[] {2, 2, 4, 1},
new int[] {5, 0, 2, 3},
new int[] {0, 6, 1, 2}
};
Console.WriteLine(maxGold(mat));
}
}
function collectGold(x, y, mat, memo) {
const n = mat.length, m = mat[0].length;
// base case
if (x < 0 || x >= n || y >= m) {
return 0;
}
// return already computed value
if (memo[x][y] !== -1) {
return memo[x][y];
}
// move to the right-upper cell
const rightUpper = collectGold(x - 1, y + 1, mat, memo);
// move directly to the right
const right = collectGold(x, y + 1, mat, memo);
// move to the right-lower cell
const rightLower = collectGold(x + 1, y + 1, mat, memo);
// store and return the max gold collected
// from the three options
memo[x][y] = mat[x][y] + Math.max(rightUpper,
right, rightLower);
return memo[x][y];
}
function maxGold(mat) {
const n = mat.length, m = mat[0].length;
let result = 0;
// initialize memo with -1
const memo =
Array.from({ length: n }, () => Array(m).fill(-1));
// try starting from each row in the first column
for (let i = 0; i < n; i++) {
const gold = collectGold(i, 0, mat, memo);
result = Math.max(result, gold);
}
return result;
}
// Driver Code
const mat = [
[1, 3, 1, 5],
[2, 2, 4, 1],
[5, 0, 2, 3],
[0, 6, 1, 2]
];
console.log(maxGold(mat));
[Better approach 2] Bottom-Up Dynamic Programming (Tabulation) - O(n×m) Space and O(n×m) Space
We define dp[x][y] as the maximum gold that can be collected starting from cell (x, y).
At each cell, we consider three possible moves: right upper (x-1, y+1), right (x, y+1), and right lower (x+1, y+1).
So the relation becomes: dp[x][y] = mat[x][y] + max(dp[x-1][y+1], dp[x][y+1], dp[x+1][y+1]), ensuring all indices are within bounds.
C++
#include <iostream>
#include <vector>
using namespace std;
int maxGold(vector<vector<int>> &mat) {
int n = mat.size(), m = mat[0].size();
// create a dp table with same dimensions
vector<vector<int>> dp(n, vector<int>(m, 0));
// fill the last column with initial gold values
for (int i = 0; i < n; i++) {
dp[i][m - 1] = mat[i][m - 1];
}
// fill the dp table from second-last column to first
for (int y = m - 2; y >= 0; y--) {
for (int x = 0; x < n; x++) {
// move to the right-upper cell
int rightUpper = (x > 0) ? dp[x - 1][y + 1] : 0;
// move directly to the right
int right = dp[x][y + 1];
// move to the right-lower cell
int rightLower = (x < n - 1) ? dp[x + 1][y + 1] : 0;
// store the max gold from the three options
dp[x][y] = mat[x][y] +
max(max(rightUpper, right), rightLower);
}
}
// find the maximum in the first column
int result = 0;
for (int i = 0; i < n; i++) {
result = max(result, dp[i][0]);
}
return result;
}
int main() {
vector<vector<int>> mat = {
{1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2}
};
cout << maxGold(mat) << endl;
return 0;
}
class GfG {
static int maxGold(int[][] mat) {
int n = mat.length, m = mat[0].length;
// create a dp table with same dimensions
int[][] dp = new int[n][m];
// fill the last column with initial gold values
for (int i = 0; i < n; i++) {
dp[i][m - 1] = mat[i][m - 1];
}
// fill the dp table from second-last column to first
for (int y = m - 2; y >= 0; y--) {
for (int x = 0; x < n; x++) {
// move to the right-upper cell
int rightUpper = (x > 0) ? dp[x - 1][y + 1] : 0;
// move directly to the right
int right = dp[x][y + 1];
// move to the right-lower cell
int rightLower = (x < n - 1) ? dp[x + 1][y + 1] : 0;
// store the max gold from the three options
dp[x][y] = mat[x][y] + Math.max(
Math.max(rightUpper, right), rightLower);
}
}
// find the maximum in the first column
int result = 0;
for (int i = 0; i < n; i++) {
result = Math.max(result, dp[i][0]);
}
return result;
}
public static void main(String[] args) {
int[][] mat = {
{1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2}
};
System.out.println(maxGold(mat));
}
}
def maxGold(mat):
n = len(mat)
m = len(mat[0])
# create a dp table with same dimensions
dp = [[0 for _ in range(m)] for _ in range(n)]
# fill the last column with initial gold values
for i in range(n):
dp[i][m - 1] = mat[i][m - 1]
# fill the dp table from second-last column to first
for y in range(m - 2, -1, -1):
for x in range(n):
# move to the right-upper cell
rightUpper = dp[x - 1][y + 1] if x > 0 else 0
# move directly to the right
right = dp[x][y + 1]
# move to the right-lower cell
rightLower = dp[x + 1][y + 1] if x < n - 1 else 0
# store the max gold from the three options
dp[x][y] = mat[x][y] + max(rightUpper, right, rightLower)
# find the maximum in the first column
result = 0
for i in range(n):
result = max(result, dp[i][0])
return result
def main():
mat = [
[1, 3, 1, 5],
[2, 2, 4, 1],
[5, 0, 2, 3],
[0, 6, 1, 2]
]
print(maxGold(mat))
main()
using System;
class GfG {
static int maxGold(int[][] mat) {
int n = mat.Length, m = mat[0].Length;
// create a dp table with same dimensions
int[][] dp = new int[n][];
for (int i = 0; i < n; i++) {
dp[i] = new int[m];
}
// fill the last column with initial gold values
for (int i = 0; i < n; i++) {
dp[i][m - 1] = mat[i][m - 1];
}
// fill the dp table from second-last column to first
for (int y = m - 2; y >= 0; y--) {
for (int x = 0; x < n; x++) {
// move to the right-upper cell
int rightUpper = (x > 0) ? dp[x - 1][y + 1] : 0;
// move directly to the right
int right = dp[x][y + 1];
// move to the right-lower cell
int rightLower = (x < n - 1) ? dp[x + 1][y + 1] : 0;
// store the max gold from the three options
dp[x][y] = mat[x][y] +
Math.Max(Math.Max(rightUpper, right), rightLower);
}
}
// find the maximum in the first column
int result = 0;
for (int i = 0; i < n; i++) {
result = Math.Max(result, dp[i][0]);
}
return result;
}
static void Main() {
int[][] mat = new int[][] {
new int[] {1, 3, 1, 5},
new int[] {2, 2, 4, 1},
new int[] {5, 0, 2, 3},
new int[] {0, 6, 1, 2}
};
Console.WriteLine(maxGold(mat));
}
}
function maxGold(mat) {
const n = mat.length, m = mat[0].length;
// create a dp table with same dimensions
const dp = Array.from({ length: n }, () => Array(m).fill(0));
// fill the last column with initial gold values
for (let i = 0; i < n; i++) {
dp[i][m - 1] = mat[i][m - 1];
}
// fill the dp table from second-last column to first
for (let y = m - 2; y >= 0; y--) {
for (let x = 0; x < n; x++) {
// move to the right-upper cell
let rightUpper = x > 0 ? dp[x - 1][y + 1] : 0;
// move directly to the right
let right = dp[x][y + 1];
// move to the right-lower cell
let rightLower = x < n - 1 ? dp[x + 1][y + 1] : 0;
// store the max gold from the three options
dp[x][y] = mat[x][y] +
Math.max(rightUpper, right, rightLower);
}
}
// find the maximum in the first column
let result = 0;
for (let i = 0; i < n; i++) {
result = Math.max(result, dp[i][0]);
}
return result;
}
// Driver Code
const mat = [
[1, 3, 1, 5],
[2, 2, 4, 1],
[5, 0, 2, 3],
[0, 6, 1, 2]
];
console.log(maxGold(mat));
[Efficient approach] Space-Optimized Tabulation – O(n×m) Time and O(n) Space
Instead of storing the entire dp[n][m] table, we only track gold values for the current and next columns using two 1D arrays: prev and curr.
We iterate from right to left, updating curr[x] using prev[x-1] -> right-upper, prev[x] -> right, and prev[x+1] -> right-lower, then swap prev and curr for the next round.
The state is given by: curr[x] = mat[x][y] + max(prev[x-1], prev[x], prev[x+1]), ensuring all indices are within bounds.
C++
#include <iostream>
#include <vector>
using namespace std;
int maxGold(vector<vector<int>> &mat) {
int n = mat.size(), m = mat[0].size();
// initialize prev with the last column of the matrix
vector<int> prev(n, 0);
for (int i = 0; i < n; i++) {
prev[i] = mat[i][m - 1];
}
// move from second-last column to the first
for (int y = m - 2; y >= 0; y--) {
vector<int> curr(n, 0);
for (int x = 0; x < n; x++) {
// move to the right-upper cell
int rightUpper = (x > 0) ? prev[x - 1] : 0;
// move directly to the right
int right = prev[x];
// move to the right-lower cell
int rightLower = (x < n - 1) ? prev[x + 1] : 0;
// store the max gold from the three options
curr[x] = mat[x][y] +
max(max(rightUpper, right), rightLower);
}
// update prev to current for the next iteration
prev = curr;
}
// find the maximum in the final prev array
int result = 0;
for (int i = 0; i < n; i++) {
result = max(result, prev[i]);
}
return result;
}
int main() {
vector<vector<int>> mat = {
{1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2}
};
cout << maxGold(mat) << endl;
return 0;
}
class GfG {
static int maxGold(int[][] mat) {
int n = mat.length, m = mat[0].length;
// initialize prev with the last column of the matrix
int[] prev = new int[n];
for (int i = 0; i < n; i++) {
prev[i] = mat[i][m - 1];
}
// move from second-last column to the first
for (int y = m - 2; y >= 0; y--) {
int[] curr = new int[n];
for (int x = 0; x < n; x++) {
// move to the right-upper cell
int rightUpper = (x > 0) ? prev[x - 1] : 0;
// move directly to the right
int right = prev[x];
// move to the right-lower cell
int rightLower = (x < n - 1) ? prev[x + 1] : 0;
// store the max gold from the three options
curr[x] = mat[x][y] +
Math.max(Math.max(rightUpper, right), rightLower);
}
// update prev to current for the next iteration
prev = curr;
}
// find the maximum in the final prev array
int result = 0;
for (int i = 0; i < n; i++) {
result = Math.max(result, prev[i]);
}
return result;
}
public static void main(String[] args) {
int[][] mat = {
{1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2}
};
System.out.println(maxGold(mat));
}
}
def maxGold(mat):
n = len(mat)
m = len(mat[0])
# initialize prev with the last column of the matrix
prev = [mat[i][m - 1] for i in range(n)]
# move from second-last column to the first
for y in range(m - 2, -1, -1):
curr = [0] * n
for x in range(n):
# move to the right-upper cell
rightUpper = prev[x - 1] if x > 0 else 0
# move directly to the right
right = prev[x]
# move to the right-lower cell
rightLower = prev[x + 1] if x < n - 1 else 0
# store the max gold from the three options
curr[x] = mat[x][y] + max(rightUpper, right, rightLower)
# update prev to current for the next iteration
prev = curr
# find the maximum in the final prev array
result = max(prev)
return result
def main():
mat = [
[1, 3, 1, 5],
[2, 2, 4, 1],
[5, 0, 2, 3],
[0, 6, 1, 2]
]
print(maxGold(mat))
main()
using System;
class GfG {
static int maxGold(int[][] mat) {
int n = mat.Length, m = mat[0].Length;
// initialize prev with the last column of the matrix
int[] prev = new int[n];
for (int i = 0; i < n; i++) {
prev[i] = mat[i][m - 1];
}
// move from second-last column to the first
for (int y = m - 2; y >= 0; y--) {
int[] curr = new int[n];
for (int x = 0; x < n; x++) {
// move to the right-upper cell
int rightUpper = (x > 0) ? prev[x - 1] : 0;
// move directly to the right
int right = prev[x];
// move to the right-lower cell
int rightLower = (x < n - 1) ? prev[x + 1] : 0;
// store the max gold from the three options
curr[x] = mat[x][y] +
Math.Max(Math.Max(rightUpper, right), rightLower);
}
// update prev to current for the next iteration
prev = curr;
}
// find the maximum in the final prev array
int result = 0;
for (int i = 0; i < n; i++) {
result = Math.Max(result, prev[i]);
}
return result;
}
static void Main() {
int[][] mat = new int[][] {
new int[] {1, 3, 1, 5},
new int[] {2, 2, 4, 1},
new int[] {5, 0, 2, 3},
new int[] {0, 6, 1, 2}
};
Console.WriteLine(maxGold(mat));
}
}
function maxGold(mat) {
const n = mat.length, m = mat[0].length;
// initialize prev with the last column of the matrix
let prev = new Array(n);
for (let i = 0; i < n; i++) {
prev[i] = mat[i][m - 1];
}
// move from second-last column to the first
for (let y = m - 2; y >= 0; y--) {
let curr = new Array(n).fill(0);
for (let x = 0; x < n; x++) {
// move to the right-upper cell
let rightUpper = (x > 0) ? prev[x - 1] : 0;
// move directly to the right
let right = prev[x];
// move to the right-lower cell
let rightLower = (x < n - 1) ? prev[x + 1] : 0;
// store the max gold from the three options
curr[x] = mat[x][y] +
Math.max(rightUpper, right, rightLower);
}
// update prev to current for the next iteration
prev = curr;
}
// find the maximum in the final prev array
let result = Math.max(...prev);
return result;
}
// Driver Code
const mat = [
[1, 3, 1, 5],
[2, 2, 4, 1],
[5, 0, 2, 3],
[0, 6, 1, 2]
];
console.log(maxGold(mat));
[Expected Approach] In-place Dynamic Programming from Right to Left - O(n×m) Time ans O(1) Space
The idea is to use in-place tabulation, traversing the matrix from right to left. For each cell mat[x][y], we calculate the maximum gold that can be collected if we come from one of the three cells in the next (right) column: mat[x-1][y+1] → right-upper, mat[x][y+1] → right, mat[x+1][y+1] → right-lower.
We update the current cell as: mat[x][y] = mat[x][y] + max(mat[x-1][y+1], mat[x][y+1], mat[x+1][y+1]).
This update is safe because we are moving right to left, so any update to mat[x][y] does not affect future calculations — the values to the right (which we depend on) have already been processed and won’t be modified again.
C++
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
bool isValid(int x, int y, int n, int m) {
return x >= 0 && x < n && y >= 0 && y < m;
}
int maxGold(vector<vector<int>> &mat) {
int n = mat.size(), m = mat[0].size();
for (int y = m - 2; y >= 0; y--) {
for (int x = 0; x < n; x++) {
int maxprev = 0;
// move from right-upper cell
if (isValid(x - 1, y + 1, n, m)) {
maxprev = max(maxprev, mat[x - 1][y + 1]);
}
// move from right cell
if (isValid(x, y + 1, n, m)) {
maxprev = max(maxprev, mat[x][y + 1]);
}
// move from right-lower cell
if (isValid(x + 1, y + 1, n, m)) {
maxprev = max(maxprev, mat[x + 1][y + 1]);
}
// store the max gold from the three options
mat[x][y] += maxprev;
}
}
// find the maximum in the first column
int result = 0;
for (int i = 0; i < n; i++) {
result = max(result, mat[i][0]);
}
return result;
}
int main() {
vector<vector<int>> mat = {
{1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2}
};
cout << maxGold(mat);
return 0;
}
class GfG {
static boolean isValid(int x, int y, int n, int m) {
return x >= 0 && x < n && y >= 0 && y < m;
}
static int maxGold(int[][] mat) {
int n = mat.length, m = mat[0].length;
for (int y = m - 2; y >= 0; y--) {
for (int x = 0; x < n; x++) {
int maxprev = 0;
// move from right-upper cell
if (isValid(x - 1, y + 1, n, m)) {
maxprev = Math.max(maxprev, mat[x - 1][y + 1]);
}
// move from right cell
if (isValid(x, y + 1, n, m)) {
maxprev = Math.max(maxprev, mat[x][y + 1]);
}
// move from right-lower cell
if (isValid(x + 1, y + 1, n, m)) {
maxprev = Math.max(maxprev, mat[x + 1][y + 1]);
}
// store the max gold from the three options
mat[x][y] += maxprev;
}
}
// find the maximum in the first column
int result = 0;
for (int i = 0; i < n; i++) {
result = Math.max(result, mat[i][0]);
}
return result;
}
public static void main(String[] args) {
int[][] mat = {
{1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2}
};
System.out.println(maxGold(mat));
}
}
def isValid(x, y, n, m):
return 0 <= x < n and 0 <= y < m
def maxGold(mat):
n = len(mat)
m = len(mat[0])
for y in range(m - 2, -1, -1):
for x in range(n):
maxprev = 0
# move from right-upper cell
if isValid(x - 1, y + 1, n, m):
maxprev = max(maxprev, mat[x - 1][y + 1])
# move from right cell
if isValid(x, y + 1, n, m):
maxprev = max(maxprev, mat[x][y + 1])
# move from right-lower cell
if isValid(x + 1, y + 1, n, m):
maxprev = max(maxprev, mat[x + 1][y + 1])
# store the max gold from the three options
mat[x][y] += maxprev
# find the maximum in the first column
result = max(mat[i][0] for i in range(n))
return result
if __name__ == "__main__":
mat = [
[1, 3, 1, 5],
[2, 2, 4, 1],
[5, 0, 2, 3],
[0, 6, 1, 2]
]
print(maxGold(mat))
using System;
class GfG {
static bool isValid(int x, int y, int n, int m) {
return x >= 0 && x < n && y >= 0 && y < m;
}
static int maxGold(int[][] mat) {
int n = mat.Length, m = mat[0].Length;
for (int y = m - 2; y >= 0; y--) {
for (int x = 0; x < n; x++) {
int maxprev = 0;
// move from right-upper cell
if (isValid(x - 1, y + 1, n, m)) {
maxprev = Math.Max(maxprev, mat[x - 1][y + 1]);
}
// move from right cell
if (isValid(x, y + 1, n, m)) {
maxprev = Math.Max(maxprev, mat[x][y + 1]);
}
// move from right-lower cell
if (isValid(x + 1, y + 1, n, m)) {
maxprev = Math.Max(maxprev, mat[x + 1][y + 1]);
}
// store the max gold from the three options
mat[x][y] += maxprev;
}
}
// find the maximum in the first column
int result = 0;
for (int i = 0; i < n; i++) {
result = Math.Max(result, mat[i][0]);
}
return result;
}
static void Main() {
int[][] mat = new int[][] {
new int[] {1, 3, 1, 5},
new int[] {2, 2, 4, 1},
new int[] {5, 0, 2, 3},
new int[] {0, 6, 1, 2}
};
Console.WriteLine(maxGold(mat));
}
}
function isValid(x, y, n, m) {
return x >= 0 && x < n && y >= 0 && y < m;
}
function maxGold(mat) {
const n = mat.length, m = mat[0].length;
for (let y = m - 2; y >= 0; y--) {
for (let x = 0; x < n; x++) {
let maxprev = 0;
// move from right-upper cell
if (isValid(x - 1, y + 1, n, m)) {
maxprev = Math.max(maxprev, mat[x - 1][y + 1]);
}
// move from right cell
if (isValid(x, y + 1, n, m)) {
maxprev = Math.max(maxprev, mat[x][y + 1]);
}
// move from right-lower cell
if (isValid(x + 1, y + 1, n, m)) {
maxprev = Math.max(maxprev, mat[x + 1][y + 1]);
}
// store the max gold from the three options
mat[x][y] += maxprev;
}
}
// find the maximum in the first column
let result = 0;
for (let i = 0; i < n; i++) {
result = Math.max(result, mat[i][0]);
}
return result;
}
// Driver Code
const mat = [
[1, 3, 1, 5],
[2, 2, 4, 1],
[5, 0, 2, 3],
[0, 6, 1, 2]
];
console.log(maxGold(mat));
Gold Mine Problem | DSA Problem
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem