Log inSign up
mediumGeeksforGeeksNot Started

Gold Mine Problem

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a gold mine of n × m dimensions. Each field in this mine contains a positive integer representing the amount of gold in tons.

Initially, the miner can start at any cell in the first column (row, 0). From a cell (row, col), the miner can move to: 1. Move to the cell diagonally up towards the right: (row - 1, col + 1) 2. Move to the cell right: (row, col + 1) 3. Move to the cell diagonally down towards the right: (row + 1, col + 1)

Find the maximum amount of gold the miner can collect until reaching the last column.

### Example 1 - Input: ``text mat = [ [1, 3, 3], [2, 1, 4], [0, 6, 4] ] ` - **Output**: 12 - **Explanation**: - Path: mat[2][0] (0) -> mat[2][1] (6) -> mat[1][2] (4)? No: - Path: mat[1][0] (2) -> mat[2][1] (6) -> mat[1][2] (4) = 2 + 6 + 4 = 12. - Max gold is 12`.

### Example 2 - Input: ``text mat = [ [1, 3, 1, 5], [2, 2, 4, 1], [5, 0, 2, 3], [0, 6, 1, 2] ] ` - **Output**: 16 - **Explanation**: mat[2][0] (5) -> mat[3][1] (6) -> mat[2][2] (2) -> mat[2][3] (3) = 16`.

Constraints:

  • 1 <= n, m <= 500
  • 0 <= mat[i][j] <= 1000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model column-progressive directional DP on 2D grids.
  • Handle multi-source starting positions in the first column.
  • Reduce 2D matrix memory to O(n) rolling column space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Grid path traversal strictly moving rightwards / diagonally right.
  • Can start at any cell in the first column.
  • Maximizing cumulative gold collected across all paths.

Algorithmic Decision Tree:

  • Strictly column-oriented transitions -> loop col on outside or update column vectors.
  • Boundary check: r - 1 >= 0 and r + 1 < n.

Connected Patterns:

Minimum Path SumTriangle Minimum Path SumMaximum Path Sum in Matrix

1. Recursive Multi-Source DFS

Intuition

From every row in column 0, recursively branch into up-right, right, and down-right cells until column m-1 is reached.

Algorithm

  1. Define dfs(r, c).
  2. If r < 0 or r >= n, return 0.
  3. If c == m - 1, return mat[r][c].
  4. Option 1: up-right dfs(r - 1, c + 1).
  5. Option 2: right dfs(r, c + 1).
  6. Option 3: down-right dfs(r + 1, c + 1).
  7. Return mat[r][c] + max({Option 1, Option 2, Option 3}).
  8. Call dfs(r, 0) for all 0 <= r < n and return max.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int dfs(int r, int c, int n, int m, const vector<vector<int>>& mat) {
8 if (r < 0 || r >= n) return 0;
9 if (c == m - 1) return mat[r][c];
10
11 int upRight = dfs(r - 1, c + 1, n, m, mat);
12 int right = dfs(r, c + 1, n, m, mat);
13 int downRight = dfs(r + 1, c + 1, n, m, mat);
14
15 return mat[r][c] + max({upRight, right, downRight});
16}
17
18int maxGoldRec(const vector<vector<int>>& mat) {
19 int n = mat.size(), m = mat[0].size();
20 int maxGold = 0;
21 for (int r = 0; r < n; r++) {
22 maxGold = max(maxGold, dfs(r, 0, n, m, mat));
23 }
24 return maxGold;
25}
26
27int main() {
28 vector<vector<int>> mat = {
29 {1, 3, 3},
30 {2, 1, 4},
31 {0, 6, 4}
32 };
33 cout << "Max Gold (Recursive): " << maxGoldRec(mat) << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(n * 3^m)
  • Space complexity: O(m) recursion stack

2. 2D Dynamic Programming Tabulation

Intuition

Build table dp[n][m] initialized with mat. Compute column-by-column from col 1 to m-1.

Algorithm

  1. Create dp matrix of size n x m copy of mat.
  2. For c = 1 to m - 1:
  3. For r = 0 to n - 1:
  4. upRight = (r > 0 ? dp[r - 1][c - 1] : 0)
  5. right = dp[r][c - 1]
  6. downRight = (r < n - 1 ? dp[r + 1][c - 1] : 0)
  7. dp[r][c] = mat[r][c] + max({upRight, right, downRight})
  8. Return the maximum value in column m - 1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int maxGold2D(const vector<vector<int>>& mat) {
8 int n = mat.size(), m = mat[0].size();
9 vector<vector<int>> dp = mat;
10
11 for (int c = 1; c < m; c++) {
12 for (int r = 0; r < n; r++) {
13 int upRight = (r > 0) ? dp[r - 1][c - 1] : 0;
14 int right = dp[r][c - 1];
15 int downRight = (r < n - 1) ? dp[r + 1][c - 1] : 0;
16 dp[r][c] = mat[r][c] + max({upRight, right, downRight});
17 }
18 }
19
20 int maxGold = 0;
21 for (int r = 0; r < n; r++) {
22 maxGold = max(maxGold, dp[r][m - 1]);
23 }
24 return maxGold;
25}
26
27int main() {
28 vector<vector<int>> mat = {
29 {1, 3, 3},
30 {2, 1, 4},
31 {0, 6, 4}
32 };
33 cout << "Max Gold (2D DP): " << maxGold2D(mat) << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(n * m)
  • Space complexity: O(n * m)

3. Space-Optimized O(n) Single Column DP

Intuition

Maintain a single 1D column array prevCol of size n representing the previous column's values.

Algorithm

  1. Initialize prevCol of size n with values from column 0.
  2. For c = 1 to m - 1:
  3. Create currCol of size n.
  4. For r = 0 to n - 1:
  5. upRight = (r > 0 ? prevCol[r - 1] : 0)
  6. right = prevCol[r]
  7. downRight = (r < n - 1 ? prevCol[r + 1] : 0)
  8. currCol[r] = mat[r][c] + max({upRight, right, downRight})
  9. prevCol = currCol
  10. Return max value in prevCol.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int maxGoldOptimal(const vector<vector<int>>& mat) {
8 int n = mat.size(), m = mat[0].size();
9 vector<int> prevCol(n);
10 for (int r = 0; r < n; r++) prevCol[r] = mat[r][0];
11
12 for (int c = 1; c < m; c++) {
13 vector<int> currCol(n);
14 for (int r = 0; r < n; r++) {
15 int upRight = (r > 0) ? prevCol[r - 1] : 0;
16 int right = prevCol[r];
17 int downRight = (r < n - 1) ? prevCol[r + 1] : 0;
18 currCol[r] = mat[r][c] + max({upRight, right, downRight});
19 }
20 prevCol = currCol;
21 }
22
23 int maxGold = 0;
24 for (int r = 0; r < n; r++) {
25 maxGold = max(maxGold, prevCol[r]);
26 }
27 return maxGold;
28}
29
30int main() {
31 vector<vector<int>> mat = {
32 {1, 3, 3},
33 {2, 1, 4},
34 {0, 6, 4}
35 };
36 cout << "Max Gold (Optimal O(n) Space): " << maxGoldOptimal(mat) << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(n * m)
  • Space complexity: O(n) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Multi-Source DFSO(n * 3^m)O(m)Exhaustive branching from all column 0 cells.Redundant paths
2.2D TabulationO(n * m)O(n * m)Matrix grid evaluated column-by-column.Full grid allocation
3.1D Column DPOptimalO(n * m)O(n)Maintain only previous column vector.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Looping row outside and column inside (corrupts dependency graph).

Pitfall 2:

Missing boundary conditions when accessing row - 1 or row + 1.

Crucial Edge Cases to Validate:

  • m = 1: Single column; output is the maximum element in that column.
  • n = 1: Single row; miner can only move straight right (output is sum of entire row).
  • All zeroes: Output is 0.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Note the contrast with standard grid problems: most grid problems move down/right (row by row), but Gold Mine moves left-to-right (column by column).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the outer loop in the Gold Mine Problem iterate over columns (from 1 to m-1) rather than rows?

Back to DSA Sheet