Gold Mine Problem

Medium
1613.

Gold Mine Problem

Gold Mine Problem is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon and Flipkart interviews.

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 <= 50
  • 0 <= mat[i][j] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} mat
 * @return {number}
 */
var maxGold = function(mat) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 50
  • 0 <= mat[i][j] <= 100

Hints for Gold Mine Problem

  1. Hint 1

    Every walk visits exactly one cell per column, moving to a neighbouring row each step.

  2. Hint 2

    Let best[r][c] be the most gold collectable starting from cell (r, c) and walking to the last column.

  3. Hint 3

    Fill best from the last column leftwards: best[r][c] = mat[r][c] + max of the up to three best values in column c + 1 at rows r - 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

  1. Copy the last column: best[r][m - 1] = mat[r][m - 1].
  2. For c from m - 2 down to 0 and every row r: best[r][c] = mat[r][c] + max(best[r'][c + 1]) over r' in {r - 1, r, r + 1} inside the grid.
  3. 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 0 gold; the answer can be 0 only 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