Gold Mine Problem — Solution in Python, Java & C++
Gold Mine Problem solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Gold Mine Problem is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon and Flipkart interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Matrix
- Asked at: Amazon, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A gold mine is an n x m grid mat, where mat[i][j] is the number of tons of gold in that cell.
A miner starts in any row of the first column. From cell (r, c) they may move to (r - 1, c + 1) (diagonally up-right), (r, c + 1) (right) or (r + 1, c + 1) (diagonally down-right), as long as the new cell is inside the grid. They collect the gold of every cell they stand on, and the walk ends in the last column.
Return the maximum amount of gold the miner can collect.
Example 1
Input: mat = [[1,3,3],[2,1,4],[0,6,4]]
Output: 12
Explanation: (1,0) → (2,1) → (2,2) or (1,2) collects 2 + 6 + 4 = 12.
Example 2
Input: mat = [[1,3,1,5],[2,2,4,1],[5,0,2,3],[0,6,1,2]]
Output: 16
Explanation: (2,0) → (3,1) → (2,2) → (2,3) collects 5 + 6 + 2 + 3; the route 5 → 6 → 1? no — but (2,0) → (1,1) → (1,2) → (0,3) collects 5 + 2 + 4 + 5 = 16.
Example 3
Input: mat = [[4],[9],[2]]
Output: 9
Explanation: With one column the miner simply picks the richest row.
Constraints
1 <= n, m <= 500 <= mat[i][j] <= 100
Hints for Gold Mine Problem
Hint 1
Every walk visits exactly one cell per column, moving to a neighbouring row each step.
Hint 2
Let
best[r][c]be the most gold collectable starting from cell(r, c)and walking to the last column.Hint 3
Fill
bestfrom the last column leftwards:best[r][c] = mat[r][c] + maxof the up to threebestvalues in columnc + 1at rowsr - 1, r, r + 1. The answer is the best entry of the first column.
How to solve Gold Mine Problem
The walk moves one column right per step, so columns give a natural order: the best haul from a cell depends only on the best hauls from its (at most three) successors in the next column.
Approach
- Copy the last column:
best[r][m - 1] = mat[r][m - 1]. - For
cfromm - 2down to0and every rowr:best[r][c] = mat[r][c] + max(best[r'][c + 1])overr' in {r - 1, r, r + 1}inside the grid. - Return
max(best[r][0])over all rows.
Why it works
From (r, c) the miner must step to one of those three cells and then continue optimally from it, so the best total from (r, c) is its own gold plus the best of the three successors. Columns to the right are always finished first, and the free choice of starting row is the final maximum over the first column.
Complexity
- Time —
O(n * m) - Space —
O(n) with one column kept at a time
Pitfalls
- Forgetting the border rows: the top row has no up-right move and the bottom row no down-right move.
- Starting only from row
0— the miner may start in any row of the first column. - Cells may hold
0gold; the answer can be0only if the whole grid is empty.
Reference solution
Python
from typing import List
def maxGold(mat: List[List[int]]) -> int:
n, m = len(mat), len(mat[0])
best = [mat[r][m - 1] for r in range(n)]
for c in range(m - 2, -1, -1):
nxt = [0] * n
for r in range(n):
top = best[r]
if r > 0 and best[r - 1] > top:
top = best[r - 1]
if r + 1 < n and best[r + 1] > top:
top = best[r + 1]
nxt[r] = mat[r][c] + top
best = nxt
return max(best)Java
public static int maxGold(int[][] mat) {
int n = mat.length, m = mat[0].length;
int[] best = new int[n];
for (int r = 0; r < n; r++) best[r] = mat[r][m - 1];
for (int c = m - 2; c >= 0; c--) {
int[] next = new int[n];
for (int r = 0; r < n; r++) {
int top = best[r];
if (r > 0) top = Math.max(top, best[r - 1]);
if (r + 1 < n) top = Math.max(top, best[r + 1]);
next[r] = mat[r][c] + top;
}
best = next;
}
int ans = 0;
for (int v : best) ans = Math.max(ans, v);
return ans;
}C++
int maxGold(vector<vector<int>>& mat) {
int n = mat.size(), m = mat[0].size();
vector<int> best(n);
for (int r = 0; r < n; r++) best[r] = mat[r][m - 1];
for (int c = m - 2; c >= 0; c--) {
vector<int> next(n);
for (int r = 0; r < n; r++) {
int top = best[r];
if (r > 0) top = max(top, best[r - 1]);
if (r + 1 < n) top = max(top, best[r + 1]);
next[r] = mat[r][c] + top;
}
best = next;
}
return *max_element(best.begin(), best.end());
}JavaScript
var maxGold = function(mat) {
var n = mat.length, m = mat[0].length;
var best = [];
for (var r = 0; r < n; r++) best.push(mat[r][m - 1]);
for (var c = m - 2; c >= 0; c--) {
var next = [];
for (var i = 0; i < n; i++) {
var top = best[i];
if (i > 0 && best[i - 1] > top) top = best[i - 1];
if (i + 1 < n && best[i + 1] > top) top = best[i + 1];
next.push(mat[i][c] + top);
}
best = next;
}
return Math.max.apply(null, best);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming