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.

Description Hints 1 Solution Video 17:24

1219. Path with Maximum Gold

Medium68.6% acceptance5 companies

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.

Asked at 5 companies

Goldman Sachs Salesforce

Google Amazon Microsoft

Topics

Hints open one at a time

Hint 1

Use recursion to try all such paths and find the one with the maximum value.

17:24

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def getMaximumGold(self, grid: List[List[int]]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[0,6,0],[5,8,7],[0,9,0]]

Input

[[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]

Your code is saved on this device.Solution