Quick Overview

Given a grid of damage and healing values, find the smallest positive starting health that lets a traveler move only right or down from the top-left cell to the bottom-right cell without health ever dropping below one. It tests dynamic programming over grid paths and precise handling of the first and last cells.

Minimum Starting Health to Cross a Grid Moving Only Right or Down

Company: Goldman Sachs

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Onsite

A grid represents a dungeon. You start in the top-left cell with some positive integer amount of health and must reach the bottom-right cell, moving one cell to the right or one cell down at each step. Every cell you occupy, including the first and the last, changes your health by its value: negative values damage you and positive values heal you. Return the minimum starting health for which some path reaches the bottom-right cell without your health ever dropping to 0 or below. ### Function Signature `min_starting_health(grid: list[list[int]]) -> int` ### Rules - Your health before entering the top-left cell is the starting health, which must be at least 1. - When you occupy cell `(r, c)`, your health changes by `grid[r][c]`. This applies to the top-left and bottom-right cells too. - After every such change, your health must be at least 1. - Health has no upper limit. - Return the smallest starting health for which at least one right/down path satisfies these rules. ### Constraints - `1 <= m <= 200` and `1 <= n <= 200`, where `m = len(grid)` and `n = len(grid[0])`; every row has length `n`. - Every cell is an integer in `[-1000, 1000]`. - The answer is at most `1 + 399 * 1000 = 399001`. ### Examples Input: `grid = [[-3,5],[-10,1]]` Output: `4` Going right and then down visits -3, 5, 1. Starting with 4 gives health 1, 6, and 7 along the way. Going down first would require at least 14. Input: `grid = [[2,-4,1],[-1,-2,3]]` Output: `2` The path down, right, right visits 2, -1, -2, 3. Starting with 2 gives health 4, 3, 1, and 4. Each of the other two paths needs a starting health of at least 3. Input: `grid = [[5]]` Output: `1` The starting health must be positive even though the only cell heals.

Overview: Given a grid of damage and healing values, find the smallest positive starting health that lets a traveler move only right or down from the top-left cell to the bottom-right cell without health ever dropping below one. It tests dynamic programming over grid paths and precise handling of the first and last cells.

You are given a two-dimensional integer grid `grid` that represents a dungeon, with `m = len(grid)` rows and `n = len(grid[0])` columns. You enter at the top-left cell `(0, 0)` with some starting health, which must be a positive integer, and you must reach the bottom-right cell `(m - 1, n - 1)`. From a cell you may move only one cell to the right or one cell down. When you occupy a cell `(r, c)` your health changes by `grid[r][c]`: negative values damage you and positive values heal you. This applies to the top-left cell and to the bottom-right cell as well. After every such change your health must be at least 1. Health has no upper limit. Return the smallest starting health for which at least one right/down path satisfies these rules. The return value is a single integer, and it is unique for every valid grid. ### Examples Example 1 Input: `grid = [[-3, 5], [-10, 1]]` Output: `4` Going right and then down visits -3, 5, 1. Starting with 4 gives health 1, 6, and 7 along the way. Going down first would require at least 14. Example 2 Input: `grid = [[2, -4, 1], [-1, -2, 3]]` Output: `2` The path down, right, right visits 2, -1, -2, 3. Starting with 2 gives health 4, 3, 1, and 4. Each of the other two paths needs a starting health of at least 3.

Constraints

  • 1 <= m <= 200 and 1 <= n <= 200, where m = len(grid) and n = len(grid[0]); every row has length n.
  • Every cell is an integer in [-1000, 1000].
  • The starting health is a positive integer, and after each cell your health must be at least 1; health has no upper limit.
  • The answer is at most 1 + 399 * 1000 = 399001.
  • No value in this problem can exceed 2^31 - 1: the answer and every intermediate requirement fit in a signed 32-bit integer, so Java may use int and C++ may use int (long / long long are not needed).

Examples

Input: ([[-3, 5], [-10, 1]],)

Expected Output: 4

Explanation: Source example 1: right then down visits -3, 5, 1, so health goes 4 -> 1 -> 6 -> 7. Going down first would require 14.

Input: ([[2, -4, 1], [-1, -2, 3]],)

Expected Output: 2

Explanation: Source example 2: down, right, right visits 2, -1, -2, 3, so health goes 2 -> 4 -> 3 -> 1 -> 4. Each other path needs at least 3.

Hints

  1. Validity is a property of every prefix of a path, not of its total: check the health after each cell, including the top-left and bottom-right ones, and notice that a path with a large total can still be fatal early.
  2. Two different ways of reaching the same cell can be compared if you know a single number about that cell. Ask what you would need to know at a cell in order to decide the rest of the trip, rather than what you have accumulated getting there.
  3. Because health must be at least 1 after every cell, any requirement you compute for a cell is itself never less than 1 — a big heal cannot lower it past that floor.

Loading coding console...

Show the approach

Approach

Work backwards from the exit instead of forwards from the entrance.

Define dp[i][j] as the minimum health you must have immediately BEFORE occupying cell (i, j) so that, taking grid[i][j] and then moving optimally to the bottom-right cell, your health is at least 1 after every cell. This quantity depends only on the suffix of the path, never on how you arrived, which is exactly why the backward direction works: a forward state would have to remember both the health accumulated so far and the worst dip so far, and those two numbers are not comparable by a single scalar.

Recurrence. At the exit, nothing follows, so the requirement after taking grid[m-1][n-1] is just 1: dp[m-1][n-1] = max(1, 1 - grid[m-1][n-1]). Elsewhere, after taking grid[i][j] you may step to (i+1, j) or (i, j+1), so you need min(dp[i+1][j], dp[i][j+1]) health at that moment, hence dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - grid[i][j]). The implementation adds a sentinel row m and column n filled with a large value so out-of-grid neighbours are never chosen, and seeds dp[m][n-1] = dp[m-1][n] = 1 so the exit cell reduces to the base case without a special branch.

Invariant and correctness. Every dp value is clamped at 1, which encodes the rule that health must stay positive after every cell; without the clamp, a large heal could 'bank' surplus health that the rules do not actually grant as a lower entry requirement. By induction on i + j decreasing, dp[i][j] is both necessary (any surviving path through (i, j) needs at least that much health on entry) and sufficient (entering with exactly dp[i][j] and following the argmin successor survives). At (0, 0) the entry health is the starting health, so dp[0][0] is the answer.

Edge cases. A 1x1 grid returns max(1, 1 - grid[0][0]), so a healing or zero cell still yields 1 because the starting health must be positive. Single-row and single-column grids collapse to the one available path. All-non-negative grids return 1. The bottom-right cell is charged like any other, so a negative exit cell raises the answer. Cells of value 0 are handled with no special case. With m, n <= 200 and cell values in [-1000, 1000], every dp value lies in [1, 399001] and every intermediate subtraction stays far inside signed 32-bit range.

Time complexity:
O(m * n)
Space complexity:
O(m * n)