Path with Maximum Gold solution and explanation
Google
9 more videos on this problem
Google Coding Interview Question - Path With Maximum Gold (LeetCode)AlgosWithMichael · 17:24 · 40K views
Path with Maximum Gold - Leetcode 1219 - PythonNeetCodeIO · 14:53 · 12K views
Path with Maximum Gold | Simplest Explanation | Leetcode 1219 | codestorywithMIKcodestorywithMIK · 21:59 · 11K views
Leetcode 1219 | Path with Maximum GoldTech Traversal · 14:54 · 5K views
1219. Path with Maximum Gold | Backtracking | RecursionAryan Mittal · 19:11 · 4K views
1219 Path with Maximum GoldKelvin Chandra · 2:24 · 1K views
Path with Maximum Gold (Leetcode 1219)Coding Interviews · 12:12 · 722 views
1219. Path with Maximum Gold - English VersionSimple Code - 단순코드 · 8:06 · 526 views
LeetCode 1219. Path with Maximum Gold | JSer - JavaScript & AlgorithmJSer · 14:21 · 511 views
LEETCODE 1219 PATH WITH MAXIMUM GOLD PYTHON | DFS leetcode questionsSasa codes · 13:09 · 487 views
The 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
0gold. - You can start and stop collecting gold from any position in the grid that has some gold.
Example 1:
Input: grid = [[0,6,0],[5,8,7],[0,9,0]] Output: 24 Explanation: [[0,6,0], [5,8,7], [0,9,0]] Path to get the maximum gold, 9 -> 8 -> 7.
Example 2:
Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]] Output: 28 Explanation: [[1,0,7], [2,0,6], [3,4,5], [0,3,0], [9,0,20]] Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 150 <= grid[i][j] <= 100- There are at most 25 cells containing gold.
Approach overview
Problem Overview: You are given an m x n grid where each cell contains some amount of gold. You can start from any cell with gold, move up/down/left/right, and cannot visit the same cell twice. The goal is to collect the maximum total gold along a valid path.
Approach 1: Backtracking with Depth-First Search (Exponential Time)
This problem naturally maps to graph traversal on a grid. Treat each gold cell as a node and explore all possible paths using DFS. Start a search from every cell with gold, recursively move in four directions, and temporarily mark the cell as visited (often by setting it to 0). After exploring a path, restore the value to allow other paths to use the cell. This classic backtracking pattern ensures every valid path is considered while preventing revisits. The time complexity is roughly O((m*n) * 4^k), where k is the number of gold cells, and space complexity is O(k) for the recursion stack. In practice, constraints are small enough that this performs well.
Approach 2: Dynamic Programming with Bitmasking
If the number of gold cells is small, you can model the problem as a state search using bitmasks. First compress the grid into a list of gold cells, then represent visited cells using a bitmask. The DP state becomes dp[mask][i], meaning the maximum gold collected when the visited set is mask and the current position is cell i. Transitions occur by moving to adjacent gold cells whose bits are not yet set. This approach converts the traversal into a graph DP similar to traveling path problems. The time complexity is about O(k * 2^k * 4) and space complexity is O(k * 2^k). It avoids repeated exploration but uses more memory.
Both approaches rely heavily on grid traversal patterns from matrix problems and adjacency checks on a 2D array. The key observation is that paths cannot revisit cells, which makes the search space manageable.
Recommended for interviews: Backtracking with DFS is the expected solution. Interviewers want to see that you can model the grid as a graph, mark cells as visited during recursion, and correctly restore state after exploring a branch. The DP with bitmasking approach demonstrates deeper optimization thinking but is rarely required unless constraints are much larger.
Approach 1: Backtracking with Depth-First Search
This approach utilizes backtracking and depth-first search (DFS) to explore all possible paths to collect the maximum gold. Start from each cell containing gold and perform DFS to explore in all four possible directions (up, down, left, right). During the search, keep track of the total gold collected. Use backtracking to unvisit a cell after exploring all potential paths from it.
class Solution:
def getMaximumGold(self, grid):
def dfs(x, y):
if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]) or grid[x][y] == 0:
return 0
originalGold = grid[x][y]
grid[x][y] = 0 # Mark as visited
maxGold = 0
# Possible directions: down, up, right, left
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
maxGold = max(maxGold, dfs(x + dx, y + dy))
grid[x][y] = originalGold # Backtrack
return originalGold + maxGold
maxGold = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] > 0:
maxGold = max(maxGold, dfs(i, j))
return maxGoldclass Solution {
private int dfs(int[][] grid, int x, int y) {
if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0) return 0;
int originalGold = grid[x][y];
grid[x][y] = 0; // Mark as visited
int maxGold = 0;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int[] dir : dirs) {
maxGold = Math.max(maxGold, dfs(grid, x + dir[0], y + dir[1]));
}
grid[x][y] = originalGold; // Backtrack
return originalGold + maxGold;
}
public int getMaximumGold(int[][] grid) {
int maxGold = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] > 0) {
maxGold = Math.max(maxGold, dfs(grid, i, j));
}
}
}
return maxGold;
}
}#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int dfs(vector<vector<int>>& grid, int m, int n, int x, int y) {
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0)
return 0;
int originalGold = grid[x][y];
grid[x][y] = 0; // Mark as visited
int maxGold = 0;
vector<pair<int, int>> directions {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (auto &dir : directions) {
maxGold = max(maxGold, dfs(grid, m, n, x + dir.first, y + dir.second));
}
grid[x][y] = originalGold; // Backtrack
return originalGold + maxGold;
}
int getMaximumGold(vector<vector<int>>& grid) {
int maxGold = 0, m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] > 0) {
maxGold = max(maxGold, dfs(grid, m, n, i, j));
}
}
}
return maxGold;
}
};var getMaximumGold = function(grid) {
const dfs = (x, y) => {
if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] === 0) return 0;
let originalGold = grid[x][y];
grid[x][y] = 0; // Mark as visited
let maxGold = 0;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (const [dx, dy] of directions) {
maxGold = Math.max(maxGold, dfs(x + dx, y + dy));
}
grid[x][y] = originalGold; // Backtrack
return originalGold + maxGold;
};
let maxGold = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] > 0) {
maxGold = Math.max(maxGold, dfs(i, j));
}
}
}
return maxGold;
};#include <stdio.h>
int dfs(int** grid, int m, int n, int x, int y) {
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0)
return 0;
int originalGold = grid[x][y];
grid[x][y] = 0; // Mark as visited
int maxGold = 0;
int directions[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
for (int i = 0; i < 4; ++i) {
maxGold = fmax(maxGold, dfs(grid, m, n, x + directions[i][0], y + directions[i][1]));
}
grid[x][y] = originalGold; // Backtrack
return originalGold + maxGold;
}
int getMaximumGold(int** grid, int gridSize, int* gridColSize) {
int maxGold = 0;
for (int i = 0; i < gridSize; ++i) {
for (int j = 0; j < gridColSize[i]; ++j) {
if (grid[i][j] > 0) {
maxGold = fmax(maxGold, dfs(grid, gridSize, gridColSize[i], i, j));
}
}
}
return maxGold;
}public class Solution {
private int DFS(int[][] grid, int x, int y) {
if (x < 0 || y < 0 || x >= grid.Length || y >= grid[0].Length || grid[x][y] == 0) return 0;
int originalGold = grid[x][y];
grid[x][y] = 0; // Mark as visited
int maxGold = 0;
int[][] directions = new int[][] { new int[] {1, 0}, new int[] {-1, 0}, new int[] {0, 1}, new int[] {0, -1} };
foreach(var dir in directions) {
maxGold = Math.Max(maxGold, DFS(grid, x + dir[0], y + dir[1]));
}
grid[x][y] = originalGold; // Backtrack
return originalGold + maxGold;
}
public int GetMaximumGold(int[][] grid) {
int maxGold = 0;
for (int i = 0; i < grid.Length; i++) {
for (int j = 0; j < grid[0].Length; j++) {
if (grid[i][j] > 0) {
maxGold = Math.Max(maxGold, DFS(grid, i, j));
}
}
}
return maxGold;
}
}The Python solution adopts a recursive depth-first search enabled by the dfs function. It systematically explores all avenues for gold collection, marking visited cells and backtracking to restore prior states when necessary. The recursive depth and methodical plotting ensure complete path examination.
Time complexity: O((m*n)^2) due to extensive backtracking traversal possibilities.
Space complexity: O(m*n) on account of recursive depth and grid modifications for pathing.
Approach 2: Dynamic Programming with Masking
This approach involves using dynamic programming with bit masking to track visited states and optimize the path of maximum gold collection. It systematically calculates the maximum gold that can be gathered by starting from each gold cell and considering valid moves while ensuring no cell is revisited.
class Solution:
def getMaximumGold(self, grid):
import functools
@functools.lru_cache(None)
def dp(mask, x, y):
maxGold = 0
for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
nx, ny = x + dx, y + dy
if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] > 0:
bit = 1 << (nx * len(grid[0]) + ny)
if not (mask & bit):
maxGold = max(maxGold, dp(mask | bit, nx, ny))
return grid[x][y] + maxGold
maxGold = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] > 0:
bit = 1 << (i * len(grid[0]) + j)
maxGold = max(maxGold, dp(bit, i, j))
return maxGoldimport java.util.*;
class Solution {
private int[][][] dp;
private final int[] dirs = {0, 1, 0, -1, 0};
private int solve(int[][] grid, int mask, int x, int y) {
if (dp[mask][x][y] != -1) return dp[mask][x][y];
int maxGold = 0;
for (int d = 0; d < 4; ++d) {
int nx = x + dirs[d], ny = y + dirs[d + 1];
if (nx >= 0 && ny >= 0 && nx < grid.length && ny < grid[0].length && grid[nx][ny] > 0
&& (mask & (1 << (nx * grid[0].length + ny))) == 0) {
int newMask = mask | (1 << (nx * grid[0].length + ny));
maxGold = Math.max(maxGold, solve(grid, newMask, nx, ny));
}
}
return dp[mask][x][y] = grid[x][y] + maxGold;
}
public int getMaximumGold(int[][] grid) {
dp = new int[1 << (grid.length * grid[0].length)][grid.length][grid[0].length];
for (int[][] arr : dp) {
for (int[] row : arr) Arrays.fill(row, -1);
}
int maxGold = 0;
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid[0].length; ++j) {
if (grid[i][j] > 0) {
int mask = 1 << (i * grid[0].length + j);
maxGold = Math.max(maxGold, solve(grid, mask, i, j));
}
}
}
return maxGold;
}
}#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
class Solution {
int dp[1 << 15][15][15];
int dirs[5] = {0, 1, 0, -1, 0};
public:
int solve(vector<vector<int>>& grid, int mask, int x, int y) {
if (dp[mask][x][y] != -1) return dp[mask][x][y];
int maxGold = 0;
for (int d = 0; d < 4; ++d) {
int nx = x + dirs[d], ny = y + dirs[d + 1];
if (nx >= 0 && ny >= 0 && nx < grid.size() && ny < grid[0].size() && grid[nx][ny] > 0
&& !(mask & (1 << (nx * grid[0].size() + ny)))) {
int newMask = mask | (1 << (nx * grid[0].size() + ny));
maxGold = max(maxGold, solve(grid, newMask, nx, ny));
}
}
return dp[mask][x][y] = grid[x][y] + maxGold;
}
int getMaximumGold(vector<vector<int>>& grid) {
memset(dp, -1, sizeof(dp));
int maxGold = 0, m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] > 0) {
int mask = 1 << (i * n + j);
maxGold = max(maxGold, solve(grid, mask, i, j));
}
}
}
return maxGold;
}
};var getMaximumGold = function(grid) {
const m = grid.length, n = grid[0].length;
const dp = [...Array(1 << (m * n))].map(() => Array(m).fill().map(() => Array(n).fill(-1)));
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
const solve = (mask, x, y) => {
if (dp[mask][x][y] !== -1) return dp[mask][x][y];
let maxGold = 0;
for (const [dx, dy] of directions) {
const nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > 0) {
const bit = 1 << (nx * n + ny);
if (!(mask & bit)) {
maxGold = Math.max(maxGold, solve(mask | bit, nx, ny));
}
}
}
dp[mask][x][y] = grid[x][y] + maxGold;
return dp[mask][x][y];
};
let maxGold = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] > 0) {
const bit = 1 << (i * n + j);
maxGold = Math.max(maxGold, solve(bit, i, j));
}
}
}
return maxGold;
};#include <stdio.h>
#include <string.h>
#define MAX 15
int dp[1 << 15][MAX][MAX]; // DP table for bit-masking
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int solve(int** grid, int rows, int cols, int mask, int x, int y) {
if (dp[mask][x][y] != -1) return dp[mask][x][y];
int maxGold = 0;
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] > 0 && !(mask & (1 << (nx * cols + ny)))) {
int newMask = mask | (1 << (nx * cols + ny));
maxGold = fmax(maxGold, solve(grid, rows, cols, newMask, nx, ny));
}
}
return dp[mask][x][y] = grid[x][y] + maxGold;
}
int getMaximumGold(int** grid, int gridSize, int* gridColSize) {
memset(dp, -1, sizeof(dp));
int rows = gridSize, cols = gridColSize[0], maxGold = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] > 0) {
int mask = 1 << (i * cols + j);
maxGold = fmax(maxGold, solve(grid, rows, cols, mask, i, j));
}
}
}
return maxGold;
}using System;
using System.Collections.Generic;
public class Solution {
private int[][][] dp;
private readonly int[] dirs = new int[] {0, 1, 0, -1, 0};
private int Solve(int[][] grid, int mask, int x, int y) {
if (dp[mask][x][y] != -1) return dp[mask][x][y];
int maxGold = 0;
for (int d = 0; d < 4; ++d) {
int nx = x + dirs[d];
int ny = y + dirs[d + 1];
if (nx >= 0 && ny >= 0 && nx < grid.Length && ny < grid[0].Length && grid[nx][ny] > 0
&& (mask & (1 << (nx * grid[0].Length + ny))) == 0) {
int newMask = mask | (1 << (nx * grid[0].Length + ny));
maxGold = Math.Max(maxGold, Solve(grid, newMask, nx, ny));
}
}
return dp[mask][x][y] = grid[x][y] + maxGold;
}
public int GetMaximumGold(int[][] grid) {
dp = new int[1 << (grid.Length * grid[0].Length)][][];
for (int i = 0; i < dp.Length; ++i) {
dp[i] = new int[grid.Length][];
for (int j = 0; j < grid.Length; ++j) {
dp[i][j] = new int[grid[0].Length];
Array.Fill(dp[i][j], -1);
}
}
int maxGold = 0;
for (int i = 0; i < grid.Length; ++i) {
for (int j = 0; j < grid[0].Length; ++j) {
if (grid[i][j] > 0) {
int mask = 1 << (i * grid[0].Length + j);
maxGold = Math.Max(maxGold, Solve(grid, mask, i, j));
}
}
}
return maxGold;
}
}The Python algorithm employs @functools.lru_cache to optimize the DP process, significantly reducing computation time through memoization techniques. This permits efficient path resolution by retaining repetitive calculations, yielding improved performance despite potential combinatorial explosion from bitmask exploration.
Time complexity: O(2^(m*n) * m * n) due to recursive state investigations.
Space complexity: O(2^(m*n) * m * n) as a result of required DP caching for computational states.
Approach 3: DFS
We can enumerate each cell as the starting point, and then start a depth-first search from the starting point. During the search process, whenever we encounter a non-zero cell, we turn it into zero and continue the search. When we can no longer continue the search, we calculate the total amount of gold in the current path, then turn the current cell back into a non-zero cell, thus performing backtracking.
The time complexity is O(m times n times 3^k), where k is the maximum length of each path. Since each cell can only be visited once at most, the time complexity will not exceed O(m times n times 3^k). The space complexity is O(m times n).
function getMaximumGold(grid: number[][]): number {
const m = grid.length;
const n = grid[0].length;
const dfs = (i: number, j: number): number => {
if (i < 0 || i >= m || j < 0 || j >= n || !grid[i][j]) {
return 0;
}
const v = grid[i][j];
grid[i][j] = 0;
let ans = v + Math.max(dfs(i - 1, j), dfs(i + 1, j), dfs(i, j - 1), dfs(i, j + 1));
grid[i][j] = v;
return ans;
};
let ans = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
ans = Math.max(ans, dfs(i, j));
}
}
return ans;
}func getMaximumGold(grid [][]int) (ans int) {
m, n := len(grid), len(grid[0])
var dfs func(i, j int) int
dfs = func(i, j int) int {
if i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0 {
return 0
}
v := grid[i][j]
grid[i][j] = 0
ans := 0
dirs := []int{-1, 0, 1, 0, -1}
for k := 0; k < 4; k++ {
ans = max(ans, v+dfs(i+dirs[k], j+dirs[k+1]))
}
grid[i][j] = v
return ans
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
ans = max(ans, dfs(i, j))
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking with Depth-First Search | Time complexity: O((m*n)^2) due to extensive backtracking traversal possibilities. Space complexity: O(m*n) on account of recursive depth and grid modifications for pathing. |
| Dynamic Programming with Masking | Time complexity: O(2^(m*n) * m * n) due to recursive state investigations. Space complexity: O(2^(m*n) * m * n) as a result of required DP caching for computational states. |
| DFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with DFS | O((m*n) * 4^k) | O(k) | Best general solution for interview constraints and typical grid sizes |
| Dynamic Programming with Bitmask | O(k * 2^k * 4) | O(k * 2^k) | When number of gold cells is small and repeated path exploration should be avoided |
Frequently asked questions
Is Path with Maximum Gold easy or hard?
Path with Maximum Gold is classified as Medium difficulty. The traversal logic is straightforward, but correctly implementing backtracking, avoiding revisits, and managing state restoration can be tricky for beginners.
How to solve Path with Maximum Gold in O(n)?
An O(n) solution is not feasible because the problem requires exploring many possible paths in the grid. The optimal practical approach uses DFS backtracking with pruning. Complexity is exponential in the number of gold cells but manageable due to small grid constraints.
What is the best approach for Path with Maximum Gold?
Backtracking with Depth-First Search is the most common approach. Start DFS from every gold cell, explore four directions, and mark cells as visited during recursion. This guarantees all valid paths are explored while preventing revisits. The complexity is roughly O((m*n) * 4^k) where k is the number of gold cells.
Is Path with Maximum Gold asked at Google/Amazon/Meta?
Grid backtracking and DFS traversal problems like Path with Maximum Gold appear frequently in interviews at companies such as Amazon, Google, and Meta. The exact question may vary, but the pattern of exploring paths in a matrix while marking visited cells is common.
What data structure is used in Path with Maximum Gold?
The problem primarily uses a 2D grid (matrix) and recursion for DFS traversal. Some optimized solutions also use bitmasks to represent visited cells in dynamic programming states. Direction arrays are commonly used to iterate through four possible moves.
What is the time complexity of Path with Maximum Gold?
The typical DFS backtracking solution runs in about O((m*n) * 4^k), where k is the number of cells containing gold. Each gold cell can branch to up to four directions, but visited checks prune many paths. Space complexity is O(k) due to recursion depth.
Path with Maximum Gold Python or Java solution approach?
Both Python and Java implementations usually follow the same DFS backtracking pattern. Start DFS from every gold cell, temporarily mark the cell as visited, explore neighbors recursively, and restore the cell value after the call. This ensures correct exploration of all paths.