Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
Run through a set of example cases:
HAPPY CASE
Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Input: [[1,1,1],[1,1,1],[1,1,1]]
Output: 9
Input: [[1,0,1],[1,0,1],[1,0,1]]
Output: 3
EDGE CASE
Input: [[1,0,90],[0,0,0],[0,0,1]]
Output: 90Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Amount of gold is positive, so we cover maximum cells of maximum values under given constraints. In every move, we move one step toward right side. So we always end up in last column. If we are at the last column, then we are unable to move right. We can perform a simple DFS starting with each cell with gold and find the maximum possible gold considering each step as a new start.
1) for each cell in the grid, start DFS. DFS state is current index and it should return starting at current index, the maximum gold it could get.
2) if current index is illegal, return 0. Otherwise, return grid[i][j] + for each direction
3) do DFS, get the maximum among 4 directions, and return.
4) before return, backtracking grid[i][j] to its original value.⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Solution:
def getMaximumGold(self, grid: List[List[int]]) -> int:
directions = [(1, 0), (-1,0), (0, 1), (0,-1)]
m, n = len(grid), len(grid[0])
self.res = 0
for i in range(m):
for j in range(n):
if grid[i][j] != 0:
visited = set()
self.dfs(i, j, 0, grid, visited, directions)
return self.res
def dfs(self, x, y, cur, grid, visited, directions):
m, n = len(grid), len(grid[0])
# 1. restraints
if x < 0 or x > m-1 or y < 0 or y > n-1 or grid[x][y]==0 or (x,y) in visited:
return
# 2. condition for adding new result
self.res = max(self.res, cur+grid[x][y])
# 3. main body for backtrack searching.
visited.add((x, y)) # mark current positio nas visited
for dx,dy in directions:
self.dfs(x+dx, y+dy, cur+grid[x][y], grid , visited, directions)
visited.remove((x, y)) # unmark current position since we returnclass Solution {
public int getMaximumGold(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int res = 0; //Intialize the result. we will be updating it accordingly
// Loop over all the valid points i.e. non zero places
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(grid[i][j] != 0){
res = Math.max(res, dfs(grid, i, j)); // Call the magical function that gives you the max gold if you start from this point and update res accordingly
}
}
}
return res;
}
public int dfs(int[][] grid, int i, int j){
if(i<0 || i>= grid.length || j<0 || j>= grid[0].length || grid[i][j] == 0) return 0; // return 0 if invalid location or the place has 0 gold or if the place is already visited
int val = grid[i][j]; // save the value of this location into a temp var
grid[i][j] = 0; // set the value of current location as 0 to mark it as visited
int left = dfs(grid, i, j-1); // traverse left
int right = dfs(grid, i, j+1); // traverse right
int up = dfs(grid, i-1, j); // traverse up
int down = dfs(grid, i+1, j); // traverse down
grid[i][j] = val; // reset the value from temp var
return grid[i][j] + Math.max(Math.max(Math.max(left,right),up),down); // get the max of all the four directions and add current value and return
}
}Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
