Path with Maximum Gold - Practice Coding Problems

Path with Maximum Gold - Problem

In a gold mine grid of size m x n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.

Return the maximum amount of gold you can collect under the conditions:

Every time you are located in a cell you will collect all the gold in that cell.
From your position, you can walk one step to the left, right, up, or down.
You can't visit the same cell more than once.
Never visit a cell with 0 gold.
You can start and stop collecting gold from any position in the grid that has some gold.

Input & Output

Example 1 — Basic Grid

$ Input: grid = [[1,2,3],[0,0,0],[7,8,9]]

› Output: 28

💡 Note: Optimal path: 7→8→9→3→2→1 collecting all gold cells. Total: 7+8+9+3+2+1 = 30. Wait, let me recalculate: We can collect 1+2+3 from top row = 6, or 7+8+9 from bottom = 24, but cannot connect them due to zeros. Best is 7→8→9 = 24.

Example 2 — Connected Path

$ Input: grid = [[1,2,3],[0,2,0],[7,0,1]]

› Output: 6

💡 Note: Best path is 1→2→3 across the top row, collecting 1+2+3 = 6 gold. The bottom cells are disconnected.

Example 3 — Single Cell

$ Input: grid = [[0,0,0],[0,1,0],[0,0,0]]

› Output: 1

💡 Note: Only one cell has gold, so maximum is 1.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 15
0 ≤ grid[i][j] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Grid with gold amounts, 0 means empty cell

Find Paths

Explore all possible paths from each gold cell

Maximum Path

Return the path with maximum total gold

Key Takeaway

🎯 Key Insight: Must explore all possible starting positions using backtracking since optimal path can begin from any gold cell

Asked in

G Google 15 a Amazon 12 M Microsoft 8 F Facebook 6

The key insight is that we must try every possible starting position since the optimal path could begin anywhere with gold. The best approach is backtracking with DFS to explore all paths while marking visited cells. Time: O(4^k) where k is gold cells, Space: O(k) for recursion stack.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS	O(4^(m×n))	O(m×n)	Try all possible paths from every valid starting cell
Optimized Backtracking	O(4^k)	O(k)	DFS with early termination and path pruning optimizations

Brute Force DFS — Algorithm Steps

Iterate through every cell in the grid
For each cell with gold > 0, start DFS
In DFS, mark current cell as visited, explore all 4 directions
Backtrack by unmarking the cell before returning

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Try starting from each cell with gold

DFS Exploration

Explore all 4 directions recursively

Backtrack

Unmark visited cells and try other paths

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int dfs(int** grid, int m, int n, int row, int col) {
    if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 0) {
        return 0;
    }
    
    int gold = grid[row][col];
    grid[row][col] = 0;
    
    int maxPath = 0;
    int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    for (int i = 0; i < 4; i++) {
        int path = dfs(grid, m, n, row + directions[i][0], col + directions[i][1]);
        if (path > maxPath) maxPath = path;
    }
    
    grid[row][col] = gold;
    
    return gold + maxPath;
}

int solution(int** grid, int m, int n) {
    if (m == 0 || n == 0) return 0;
    
    int maxGold = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] > 0) {
                int gold = dfs(grid, m, n, i, j);
                if (gold > maxGold) maxGold = gold;
            }
        }
    }
    
    return maxGold;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for small grids
    int** grid = (int**)malloc(4 * sizeof(int*));
    for (int i = 0; i < 4; i++) {
        grid[i] = (int*)malloc(4 * sizeof(int));
    }
    
    // Parse [[1,2],[3,4]] format manually
    int m = 0, n = 0;
    char* ptr = line;
    while (*ptr && m < 4) {
        if (*ptr == '[' && *(ptr-1) != '[') {
            ptr++;
            n = 0;
            while (*ptr && *ptr != ']' && n < 4) {
                if (*ptr >= '0' && *ptr <= '9') {
                    grid[m][n] = 0;
                    while (*ptr >= '0' && *ptr <= '9') {
                        grid[m][n] = grid[m][n] * 10 + (*ptr - '0');
                        ptr++;
                    }
                    n++;
                } else {
                    ptr++;
                }
            }
            m++;
        }
        ptr++;
    }
    
    printf("%d\n", solution(grid, m, n));
    
    for (int i = 0; i < 4; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4^(m×n))

In worst case, we explore all possible paths from each cell, with 4 choices at each step

✓ Linear Growth

Space Complexity

O(m×n)

Recursion depth can go up to m×n cells in the worst case

⚡ Linearithmic Space

89.0K Views

Medium Frequency

~25 min Avg. Time

2.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler