Path with Maximum Gold

MediumBacktrackingbacktracking

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A mine is an m x n grid where grid[i][j] is the amount of gold in that cell, and 0 means the cell is empty and cannot be entered. You may start at any cell with gold and move one step up, down, left, or right at a time, collecting all the gold in every cell you enter. You can never enter a cell with 0 gold and can never visit the same cell twice in one path. You may stop at any time. Return the maximum total gold you can collect. If the grid has no gold, return 0.

Examples

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
The path 9 -> 8 -> 7 collects 24.
Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
The path 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 collects 28.

Constraints

  • `1 <= m, n <= 15`
  • `0 <= grid[i][j] <= 100`
  • At most 25 cells contain gold

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More backtracking problems