Abstract / Summary

A knight must find the minimal initial health to reach the bottom right from the top left in a dungeon with positive and negative health cells.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 42% (700k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming
• Matrix

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes the minimum initial health required for a knight to survive a grid-based dungeon, moving only rightward or downward. It works backwards from the destination cell, propagating the health requirement to predecessor cells until the start cell is resolved. The algorithm stores intermediate results in a two-dimensional array and uses an explicit stack to drive the propagation.

Key Steps

Dimension Extraction and Matrix Allocation

width  = len(dungeon[0])
height = len(dungeon)

hp = []
for y in range(height):
    hp.append([ 999999999 ] * width)

The code first determines the grid dimensions and creates a matrix hp of the same size, filled with a large sentinel value. This sentinel represents an unknown or infinitely large health requirement before any computation.

Base Case Initialization

hp[height-1][width-1] = 1 - min(0, dungeon[height-1][width-1])

The destination cell is initialized to the minimum health needed to survive that cell. If the cell contains a non-positive value, the knight must have at least 1 - cell_value health; otherwise a single health point suffices.

Stack Preparation

todo = []
if width > 1 or height > 1:
    todo = [ [ height-1, width-1] ]

When the grid contains more than one cell, the bottom-right coordinate is placed on a stack named todo. This stack drives the reverse traversal.

Reverse Propagation Loop

while todo:
    y, x = todo.pop()
    health = hp[y][x]

    if x > 0:
        need = max(1, health - dungeon[y][x-1])
        if hp[y][x-1] > need:
            hp[y][x-1] = need
            todo.append([ y, x-1 ])
    if y > 0:
        need = max(1, health - dungeon[y-1][x])
        if hp[y-1][x] > need:
            hp[y-1][x] = need
            todo.append([ y-1, x ])

Inside the loop the algorithm extracts a cell from the stack, reads its current health requirement, and examines its left and upper neighbours (the only cells that can move into the current one). For each neighbour it computes the health needed to step into the current cell, ensuring the result never drops below one. If this computed requirement improves the neighbour’s stored value, the neighbour is updated and pushed onto the stack for further propagation.

Result Retrieval

return hp[0][0]

After the stack is exhausted, the top-left entry of hp holds the minimum initial health needed at the start of the dungeon.

Edge Cases Handled

When the dungeon consists of a single cell, the stack is left empty because no propagation is required. The base case assignment directly yields the correct answer for that scenario.

If a cell contains a large positive number, the max(1, ...) guard ensures that the health requirement never falls below one, preventing an underflow to zero or negative health.

When a cell contains a large negative number, the subtraction health - dungeon[...] correctly increases the required health, and the sentinel value 999999999 guarantees that the first computed need will replace it.

Zero-valued cells are treated like neutral rooms; the max(1, ...) clause still enforces a minimum of one health point, satisfying the rule that the knight must stay alive after each move.

Performance Optimizations

The algorithm avoids recursion by using an explicit stack, eliminating the overhead of function call management and enabling in-place updates of the hp matrix.

The sentinel value initialization prevents repeated boundary checks inside the loop; each cell’s health requirement is only updated when a strictly better (lower) value is found, reducing unnecessary stack pushes.

The use of max(1, ...) consolidates the lower-bound enforcement into a single arithmetic operation, avoiding separate conditional branches for positive and negative adjustments.

By updating neighbours only when the new requirement is smaller than the existing entry, the code minimizes the number of times a cell is revisited, leading to fewer iterations of the main loop.

Overall, the design leverages a forward-compatible data structure (hp) and a depth-first style stack to propagate constraints efficiently across the grid.

Imagine a big castle made of many square rooms laid out like a floor made of tiles. Inside some of these rooms are magic treasure chests that give a knight extra energy, and in other rooms are mean dragons that take energy away. The goal is for the knight to walk from the very last room back to the very first room while always staying strong enough to survive the dragons.

The computer starts at the very end of the castle and figures out exactly how much energy is needed at the last tile to make it through safely. It then looks at the tiles right before that one. It thinks about whether the knight would need more or less energy to pass through the dragon in the previous room.

A list called todo helps the computer keep track of which rooms it still needs to check. It picks a room from this list and looks at the neighbors to the left and above it. It calculates the minimum amount of energy required to face whatever is in those neighboring rooms. If the computer finds a smaller number than it saw before, it remembers that new amount and adds that room to the list so it can look at the ones before that too.

By working backward from the end to the start, the computer builds a map of the exact energy needed at every step of the journey. Once the computer works its way all the way back to the very first room at the beginning of the castle, it knows exactly how much energy is needed to start the adventure so that the knight can get through the whole castle without ever running out.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python			Java				TS
	WalkCCC	C++	Python			Java
	leetcode.ca	C++	Python			Java	C#	Go
	LeetcodeHelp	C++	Python			Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python			Java
github	aylei			Rust
	begeekmyfriend								C
	BigEggStudy						C#
	black-shadows		Python
	charles-wangkai					Java
	chenyanzhe	C++
	everthis				JS
	fpdjsns	C++
	gaosq0604		Python
	gouthampradhan					Java
	halfrost							Go
	haoel	C++
	JoshCrozier				JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	ruoru			Rust
	suxrobGM						C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	Python, Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fpdjsns	C++
gaosq0604	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
MacJim	C++
ruoru	Rust
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality