Scale Engineer

Path with Maximum Gold

Med
#1138Time: O(m*n + k! * k^2), where `m` and `n` are the grid dimensions and `k` is the number of gold cells. The `k!` term comes from generating all permutations, making this approach impractical.Space: O(k^2) to store gold cell locations and potentially an adjacency matrix for efficient checks. The space to hold a single permutation is O(k).1 company
Patterns
Backtracking
Data structures
ArrayMatrix
Companies
Geico

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves generating all possible sequences of gold cells and checking if they form a valid path. It's a straightforward but highly inefficient method. We first identify all cells with gold. Then, we generate all permutations of these cells. For each permutation, we check all its prefixes to see if they constitute a valid path (i.e., consecutive cells are adjacent in the grid). If a path is valid, we compute its total gold and update our maximum. This method is too slow for the given constraints due to the factorial growth in the number of permutations.

Algorithm

  • Identify all k cells with gold in the grid.
  • Generate all k! permutations of these gold cells.
  • For each permutation, iterate through all its prefixes (from length 1 to k).
  • For each prefix, check if it forms a valid path by ensuring all consecutive cells are adjacent.
  • If the path is valid, calculate the sum of gold and update the global maximum.
  • Return the global maximum after checking all possibilities.

Walkthrough

The brute-force algorithm proceeds as follows:

  1. Find Gold Cells: Traverse the entire m x n grid to locate all cells with gold. Store their coordinates and values, say in a list of k cells.
  2. Generate Permutations: Generate all possible orderings (permutations) of these k cells. There are k! such permutations.
  3. Validate Paths and Calculate Gold: For each permutation, we must treat it as a potential path. Since a path can start and stop anywhere, we must check every prefix of the permutation.
    • For a prefix of length L, we verify if it's a valid path. This means checking that for each i from 0 to L-2, the cell at index i in the sequence is adjacent (up, down, left, or right) to the cell at index i+1.
    • If the prefix is a valid path, we sum the gold values of the cells in it.
    • We keep track of the maximum sum found across all valid paths from all permutations.
  4. Return Maximum: After exhausting all possibilities, the maximum sum recorded is the answer.

This approach is not practical due to its factorial time complexity. For k=25, 25! is an astronomically large number, making the computation impossible.

Complexity

Time

O(m*n + k! * k^2), where `m` and `n` are the grid dimensions and `k` is the number of gold cells. The `k!` term comes from generating all permutations, making this approach impractical.

Space

O(k^2) to store gold cell locations and potentially an adjacency matrix for efficient checks. The space to hold a single permutation is O(k).

Trade-offs

Pros

  • Conceptually simple to understand.

Cons

  • Extremely high time complexity (O(k!)), making it infeasible for k larger than about 10.

  • Complex to implement correctly.

Solutions

class Solution {private  final int[] dirs = {-1, 0, 1, 0, -1};private  int[][] grid;private  int m;private  int n;public  int getMaximumGold(int[][] grid) {    m = grid.length;    n = grid[0].length;    this.grid = grid;    int ans = 0;    for (int i = 0; i < m; ++i) {      for (int j = 0; j < n; ++j) {        ans = Math.max(ans, dfs(i, j));      }    }    return ans;  }private  int dfs(int i, int j) {    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {      return 0;    }    int v = grid[i][j];    grid[i][j] = 0;    int ans = 0;    for (int k = 0; k < 4; ++k) {      ans = Math.max(ans, v + dfs(i + dirs[k], j + dirs[k + 1]));    }    grid[i][j] = v;    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem