FastPrepMinimum-Weight Top-to-Bottom Grid Path
Problem · Matrix

Minimum-Weight Top-to-Bottom Grid Path

Learn this problem
● MediumGoogle logoGoogleFULLTIMEONSITE INTERVIEW
See Google hiring insights

Problem statement

You are given a rectangular matrix weights. A value of -1 marks a blocked cell. Every other value is a positive traversal cost.

You may start at any unblocked cell in the top row. From an unblocked cell, you may move one cell up, down, left, or right, staying inside the matrix and never entering a blocked cell.

The cost of a path is the sum of the weights of every cell in the path, including its starting and ending cells. Return the minimum possible cost of reaching any unblocked cell in the bottom row. Return -1 if no such path exists.

Function

minimumTopToBottomPath(weights: int[][]) → long

Examples

Example 1

weights = [[1,50,50,50],[1,1,1,50],[50,50,1,50]]return = 5

The cheapest path is (0,0) -> (1,0) -> (1,1) -> (1,2) -> (2,2), with total cost 1 + 1 + 1 + 1 + 1 = 5. It uses more moves than the direct expensive routes.

Example 2

weights = [[5,1,5],[1,-1,1],[1,1,1]]return = 7

Starting at (0,0) and moving down twice costs 5 + 1 + 1 = 7. The low-cost top-middle cell cannot move down through the blocked center and needs a more expensive detour.

Example 3

weights = [[1,-1],[-1,-1]]return = -1

No unblocked bottom-row cell is reachable from the only unblocked top-row cell.

Constraints

  • 1 <= weights.length <= 500
  • 1 <= weights[i].length <= 500
  • Every row has the same length.
  • Every cell is -1 or an integer in [1, 10^6].
  • A move changes the row or column by exactly 1, but not both.

More Google problems

drafts saved locally
public long minimumTopToBottomPath(int[][] weights) {
    // Write your code here.
}
weights[[1,50,50,50],[1,1,1,50],[50,50,1,50]]
expected5
checking account