The least starting health
A knight starts at the top-left cell of a grid and must reach the bottom-right cell, moving only right or down. Each cell changes his health by its value (negative cells hurt, positive cells heal), including the first and last cells. If his health ever drops to 0 or below, he dies. Return the least positive starting health that lets him arrive alive.
Examples
| Input | Output | Why |
|---|---|---|
dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] | 7 | Right, right, down, down: health 7 → 5 → 2 → 5 → 6 → 1. |
dungeon = [[0]] | 1 | Health must start positive. |
dungeon = [[-10]] | 11 | He needs 11 to survive losing 10. |
Constraints
- 1 ≤ rows, cols ≤ 200
- −1000 ≤ dungeon[r][c] ≤ 1000
Hints
Hint 1
Going forwards, you would need to track both health and the lowest point reached: two things to optimise at once.
Hint 2
Going backwards, need[r][c] = the least health on entering (r, c) that guarantees survival from there.
Hint 3
need[r][c] = max(1, min(need below, need right) − dungeon[r][c]).
Where people lose marks
- Filling forwards with the maximum health so far, which ignores dips along the way.
- Forgetting the max with 1, so a large heal later "pays for" dying earlier.
- Not applying the start cell's own value.
Dry run on [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 9
(2, 2) with value -5: need max(1, 1 − (-5)) = 6.
-
Step 2 / 9
(2, 1) with value 30: need max(1, 6 − (30)) = 1.
-
Step 3 / 9
(2, 0) with value 10: need max(1, 1 − (10)) = 1.
-
Step 4 / 9
(1, 2) with value 1: need max(1, 6 − (1)) = 5.
-
Step 5 / 9
(1, 1) with value -10: need max(1, 1 − (-10)) = 11.
-
Step 6 / 9
(1, 0) with value -5: need max(1, 1 − (-5)) = 6.
-
Step 7 / 9
(0, 2) with value 3: need max(1, 5 − (3)) = 2.
-
Step 8 / 9
(0, 1) with value -3: need max(1, 2 − (-3)) = 5.
-
Step 9 / 9
(0, 0) with value -2: need max(1, 5 − (-2)) = 7. He must start with 7.
How to think about it
Filling forwards fails: the best path to a cell might arrive with plenty of health but have dipped dangerously on the
way, and a single number per cell cannot capture both. Filling backwards works, because the question at each cell is
self-contained: what is the least health needed on entering (r, c) to survive the rest? From the end:
need = max(1, 1 − dungeon[end]); elsewhere need[r][c] = max(1, min(need[r + 1][c], need[r][c + 1]) −
dungeon[r][c]). The max with 1 says health may never fall below 1, however much a later cell would heal.
Complexity. Time O(rows · cols) · Space O(cols)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def minimum_health(dungeon):
rows, cols = len(dungeon), len(dungeon[0])
INF = float('inf')
need = [INF] * (cols + 1) # need for the row below; need[cols] is outside the grid
for r in range(rows - 1, -1, -1):
for c in range(cols - 1, -1, -1):
if r == rows - 1 and c == cols - 1:
after = 1 # leave the last cell with at least 1
else:
after = min(need[c], need[c + 1]) # below (old value) or right (new value)
need[c] = max(1, after - dungeon[r][c])
need[cols] = INF
return need[0]#include <algorithm>
#include <climits>
#include <vector>
long long solve(const std::vector<std::vector<int>>& dungeon) {
const int rows = dungeon.size(), cols = dungeon[0].size();
const long long INF = LLONG_MAX / 4;
std::vector<long long> need(cols + 1, INF);
for (int r = rows - 1; r >= 0; --r)
for (int c = cols - 1; c >= 0; --c) {
long long after = (r == rows - 1 && c == cols - 1) ? 1 : std::min(need[c], need[c + 1]); // below or right
need[c] = std::max(1LL, after - dungeon[r][c]);
}
return need[0];
}class Solution {
public long minimumHealth(int[][] dungeon) {
int rows = dungeon.length, cols = dungeon[0].length;
long inf = Long.MAX_VALUE / 4;
long[] need = new long[cols + 1];
java.util.Arrays.fill(need, inf);
for (int r = rows - 1; r >= 0; r--)
for (int c = cols - 1; c >= 0; c--) {
long after = (r == rows - 1 && c == cols - 1) ? 1 : Math.min(need[c], need[c + 1]); // below or right
need[c] = Math.max(1, after - dungeon[r][c]);
}
return need[0];
}
}function minimumHealth(dungeon) {
const rows = dungeon.length, cols = dungeon[0].length;
const need = new Array(cols + 1).fill(Infinity);
for (let r = rows - 1; r >= 0; r--)
for (let c = cols - 1; c >= 0; c--) {
const after = r === rows - 1 && c === cols - 1 ? 1 : Math.min(need[c], need[c + 1]); // below or right
need[c] = Math.max(1, after - dungeon[r][c]);
}
return need[0];
}fn solve<const C: usize>(dungeon: &[[i64; C]]) -> i64 {
let rows = dungeon.len();
let inf = i64::MAX / 4;
let mut need = vec![inf; C + 1];
for r in (0..rows).rev() {
for c in (0..C).rev() {
let after = if r == rows - 1 && c == C - 1 { 1 } else { need[c].min(need[c + 1]) }; // below or right
need[c] = 1i64.max(after - dungeon[r][c]);
}
}
need[0]
}solve :: [[Int]] -> Int
solve dungeon = case foldr rowUp Nothing dungeon of
Just (x : _) -> x
_ -> 1
where
width = length (head dungeon)
inf = maxBound `div` 2 :: Int
-- each row's needs from the row below; Nothing stands for "below the last row"
rowUp row below = Just (foldr cell [] (zip3 [0 ..] row belowRow))
where
belowRow = maybe (replicate width inf) id below
cell (c, v, down) acc =
let right = case acc of { (x : _) -> x; [] -> inf }
after = if below == Nothing && c == width - 1 then 1 else min down right
in max 1 (after - v) : accVariants to try
- Return the path.
- Moves in all four directions with no revisits (no longer a DP over a DAG).
- A binary search on the starting health with a forward check: correct but slower.
Next problems
The cheapest path through a grid
Move only right or down from the top-left cell to the bottom-right one, paying each cell's cost. Each cell's cheapest arrival comes from above or the left.
Open the problem → Medium15 minPaths around obstacles
Count the paths from the top-left to the bottom-right cell, moving right or down and never entering an obstacle.
Open the problem → Medium20 minThe largest square of ones
Find the area of the largest all-ones square in a 0/1 grid. The square ending at a cell is limited by the three squares ending next to it.
Open the problem →Write a solution and run it against the real test table.
Keep going
The cheapest path through a grid
Move only right or down from the top-left cell to the bottom-right one, paying each cell's cost. Each cell's cheapest arrival comes from above or the left.
Open the problem → Medium15 minPaths around obstacles
Count the paths from the top-left to the bottom-right cell, moving right or down and never entering an obstacle.
Open the problem → Medium20 minThe largest square of ones
Find the area of the largest all-ones square in a 0/1 grid. The square ending at a cell is limited by the three squares ending next to it.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.