Home » Interview coding problems/challenges

# Gold Mine Problem

**Gold Mine Problem**: Here, we are going to learn about the Gold Mine Problem, its solution. This is a standard interview problem featured in coding rounds of Amazon, Flipkart.

Submitted by Radib Kar, on February 07, 2020

**Description:**

This is a standard interview problem featured in interview coding rounds of Amazon, Flipkart.

**Problem statement:**

**Given a gold mine** of **n*m dimensions**, each cell in this mine contains a positive integer which is the amount of gold in tons. Initially, the miner is at the first column but can be at any row. He can move only right or right up or right down from the current cell, i.e., the miner can move to the cell diagonally up towards the right or right or diagonally down towards the right. Find out the maximum amount of gold he can collect.

Input: Matrix: {{1,5,12}, {2,4,4}, {0,6,4} {3,0,0} } Output: 18 Input: Matrix: {{1,3,1,5}, {2,2,4,1}, {5,0,2,3}, {0,6,11,2} } Output: 25

**Explanation with example**

So, the matrix is:

So, the miner starts from the first column (any row) and he has to reach the last row with maximum gold.

To make a note, the possible moves from a cell **(i,j)** is to either of,

Now, it seems apparently that greedy may work for the problem that is at the first column pick the cell with maximum value and then move to next best neighbouring cell.

If we follow the above greedy approach,

We would pick **(3,0)** as our starting cell since that contains maximum gold out of the first column. The next best move would be **(2,1)** and then to **(2,2)**.

So, the total gold collected is = **(3+6+4) = 13**

Is this the global maximum? Do our local maximum choices lead to global maximum?

No, it's not the global maximum.

The global maximum path would be: **(1,0) ->(0,1)->(0,2)**

Total coin that can be achieved: **(2+5+12) = 19**

So, the local best choices don't lead to the global best and hence we need dynamic programming.

**Solution Approach:**

Create a DP matrix of dimension m*n: **DP[m][n]**

The first column of the DP matrix would be same as the input matrix. Rest of the columns are 0,

for i=0 to n-1 DP[i][0]=arr[i][0];

For the other columns, update DP value for every row. For every cell **(i,j)** update like following way.

**So, for the earlier input matrix,**

**After completion of the First column (row wise computing),**

**After completion of second column (row wise computation),**

Now find the maximum of the final column, that's the maximum gold that can be collected.

**Result=19**

**C++ implementation:**

#include <bits/stdc++.h> using namespace std; int GoldMine(int** arr, int n, int m) { //DP table int DP[n][m]; memset(DP, 0, sizeof(DP)); for (int i = 0; i < n; i++) DP[i][0] = arr[i][0]; //for every column for (int j = 1; j < m; j++) { //check which option is better accordingly for (int i = 0; i < n; i++) { //choosing max of possible moves DP[i][j] = arr[i][j]; int val = DP[i][j - 1]; if (i - 1 >= 0) { if (val < DP[i - 1][j - 1]) val = DP[i - 1][j - 1]; } if (i + 1 < n) { if (val < DP[i + 1][j - 1]) val = DP[i + 1][j - 1]; } DP[i][j] += val; } } // find the maximum of the last column int gold = DP[0][m - 1]; for (int i = 1; i < n; i++) { if (DP[i][m - 1] > gold) gold = DP[i][m - 1]; } return gold; } int main() { int n, item, m; cout << "Enter matrix dimensions, m & n\n"; cin >> n >> m; cout << "Input matrix cells\n"; int** arr = (int**)(malloc(sizeof(int*) * n)); //input array for (int j = 0; j < n; j++) { arr[j] = (int*)(malloc(sizeof(int) * m)); for (int k = 0; k < m; k++) cin >> arr[j][k]; } cout << "Max amount of gold that can be collected: " << GoldMine(arr, n, m) << endl; return 0; }

**Output**

Enter matrix dimensions, m & n 4 3 Input matrix cells 1 5 12 2 4 4 0 6 4 3 0 0 Max amount of gold that can be collected: 19

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.