FastPrepMinimum Starting Health in a Grid
Problem · Matrix

Minimum Starting Health in a Grid

Learn this problem
● HardIntuit logoIntuitINTERNOA

Problem statement

You are given a non-empty rectangular integer matrix grid. Start at the top-left cell and reach the bottom-right cell by moving only right or down.

Entering a cell immediately adds that cell's value to your current health. Health may become exactly 0, but it must never become negative.

Return the minimum nonnegative health required before entering grid[0][0] so that at least one valid path reaches the destination without health becoming negative.

Function

minimumStartingHealth(grid: int[][]) → int

Examples

Example 1

grid = [[-2,-3,3],[-5,-10,1],[10,30,-5]]return = 6

With starting health 6, the path right, right, down, down produces health 4, 1, 4, 5, 0. Starting with less would make health negative along every valid path.

Example 2

grid = [[5]]return = 0

Starting with 0 is allowed, and entering the only cell raises health to 5.

Example 3

grid = [[-4,10],[-10,-1]]return = 4

Starting with 4 and moving right then down gives health 0, 10, 9. Any smaller start becomes negative in the first cell.

Constraints

  • 1 <= grid.length <= 200.
  • 1 <= grid[i].length <= 200.
  • Every row has the same length.
  • grid.length * grid[0].length <= 40000.
  • -1000 <= grid[i][j] <= 1000.

More Intuit problems

drafts saved locally
public int minimumStartingHealth(int[][] grid) {
    // Write your code here
}
grid[[-2,-3,3],[-5,-10,1],[10,30,-5]]
expected6
checking account