Skip to main content
Talentd

Path with Maximum Gold - Solution & Explanation

MediumArrayBacktrackingMatrix21 min readAsked at: Amazon, Microsoft, Goldman Sachs +2
Practice this problem

Problem Statement

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.

 

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.length
  • n == grid[i].length
  • 1 <= m, n <= 15
  • 0 <= 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.

The C language implementation uses a recursive function 'dfs' to explore each valid path starting from a gold cell. It employs a grid to mark visited cells by setting their gold value to zero and restores them after backtracking is complete. This way, all potential paths can be explored to determine the path with the maximum gold.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O((m*n)^2) - In the worst-case scenario, each cell containing gold gets visited and backtracked.

Space complexity: O(m*n) - This results from recursive stack space and the grid modifications.

Try this approach in the editor →

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.

This implementation uses a bitmask to track visited states and dynamic programming to store interim computations. It only traverses unvisited gold-bearing cells and optimizes path selection for maximal gold collection efficiency. State visits are held in a DP table indexed by the bitmask, with recursive exploration to uncover superior paths.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(2^(m*n) * m * n) given bitmask state examination.

Space complexity: O(2^(m*n) * m * n) due to DP storage needs for various path states.

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking with Depth-First Search

Time complexity: O((m*n)^2) - In the worst-case scenario, each cell containing gold gets visited and backtracked.

Space complexity: O(m*n) - This results from recursive stack space and the grid modifications.

Dynamic Programming with Masking

Time complexity: O(2^(m*n) * m * n) given bitmask state examination.

Space complexity: O(2^(m*n) * m * n) due to DP storage needs for various path states.

DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with DFSO((m*n) * 4^k)O(k)Best general solution for interview constraints and typical grid sizes
Dynamic Programming with BitmaskO(k * 2^k * 4)O(k * 2^k)When number of gold cells is small and repeated path exploration should be avoided

Video Solution

Google Coding Interview Question - Path With Maximum Gold (LeetCode) • AlgosWithMichael • 40,669 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Path with Maximum Gold with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays