Abstract / Summary

Find the minimum effort path between two points in a grid where effort is the maximum difference in heights along the path.

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 63% (700k+ submissions).

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 minimumEffortPath method computes the smallest possible effort required to travel from the top-left cell to the bottom-right cell of a rectangular grid. Effort for a path is defined as the maximum absolute difference in height between any two consecutive cells along that path. The algorithm works backward from the destination, propagating the minimal effort needed to reach the destination from each cell.

Initialization

The dimensions of the grid are extracted, and an auxiliary matrix named effort is created to store the best known effort from each cell to the target. Every entry is seeded with a very large sentinel value, effectively representing “infinite” effort, except for the destination cell which is initialized to zero because no movement is required to stay there. A list called todo holds the frontier of cells whose neighbors still need to be examined; it starts with the destination coordinates.

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

effort = []
for _ in range(height):
    effort.append([ 9999999999 ] * width)
effort[height-1][width-1] = 0

todo = [ [ width-1, height-1 ] ]

Propagation Loop

The core of the solution is a loop that continues until there are no more cells to process. For each cell taken from todo, the four orthogonal neighbors are examined. The potential effort to reach the destination via the current cell is the larger of two values: the effort already recorded for the current cell and the absolute height difference between the current cell and the neighbor. If this computed value improves the neighbor’s stored effort, the neighbor is updated and added to the next frontier list. After all cells in the current frontier are processed, todo is replaced by the newly built list, and the loop repeats.

while todo:
    next = []
    for x, y in todo:
        if x > 0:
            path = max(effort[y][x], abs(heights[y][x-1] - heights[y][x]))
            if effort[y][x-1] > path:
                effort[y][x-1] = path
                next.append([ x-1, y ])
        if x < width-1:
            path = max(effort[y][x], abs(heights[y][x+1] - heights[y][x]))
            if effort[y][x+1] > path:
                effort[y][x+1] = path
                next.append([ x+1, y ])
        if y > 0:
            path = max(effort[y][x], abs(heights[y-1][x] - heights[y][x]))
            if effort[y-1][x] > path:
                effort[y-1][x] = path
                next.append([ x, y-1 ])
        if y < height-1:
            path = max(effort[y][x], abs(heights[y+1][x] - heights[y][x]))
            if effort[y+1][x] > path:
                effort[y+1][x] = path
                next.append([ x, y+1 ])
    todo = next

When the loop finishes, the entry effort[0][0] holds the minimal effort required to travel from the start to the destination, and it is returned.

return effort[0][0]

Edge Cases Handled

The algorithm gracefully handles a grid consisting of a single cell. In that situation width and height are both one, the effort matrix contains a single zero, and the todo list starts with the only cell. The while loop processes that cell, finds no valid neighbors because all boundary checks fail, and immediately exits, returning zero - the correct effort for a trivial path.

Boundary checks (x > 0, x < width-1, y > 0, y < height-1) ensure that attempts to access neighbors never go out of range, even for cells located on the edges or corners of the grid. The use of abs guarantees that height differences are treated uniformly regardless of whether the neighbor is higher or lower.

Large variations in height are accommodated because the effort for a path is always the maximum of the current path effort and the newly encountered height difference. Consequently, a single steep climb or descent dominates the effort value, matching the problem definition.

Performance Optimizations

The implementation avoids the overhead of a priority queue by using a breadth-first style expansion that only enqueues a neighbor when a strictly better effort value is discovered. This pruning prevents redundant processing of cells whose effort cannot improve, reducing the number of iterations. The effort matrix is updated in place, eliminating the need for auxiliary data structures to track visited status. The sentinel value 9999999999 is a constant that fits comfortably within Python’s integer range, allowing fast comparisons without additional function calls. Finally, the frontier lists todo and next are simple Python lists; appending to them is amortized O(1), and swapping references (todo = next) reuses the allocated memory without extra copying. These choices collectively keep the runtime tight while maintaining clear and straightforward code flow.

Imagine a big grid of mountains that looks like a giant checkerboard. Some spots are very tall and some are low, and walking between them is like going up and down a hilly path. This code is trying to find the easiest way to walk from one corner of the mountains to the other.

First, it marks every single spot on the map with a really big number. This is just a way of saying that the path is unknown for now. It starts at the very end of the trail and sets the effort there to zero because reaching the finish line already counts as being finished.

Then, it looks at all the neighbors of the current spot. It checks the mountains to the left, right, up, and down to see how big the step is between them. If it finds a way to move that is smaller than the current effort, it updates the map with that new, better number.

It keeps doing this over and over, moving from square to square like a explorer. By checking every neighbor and picking the smallest jump, it slowly learns the easiest route through the landscape. When it finally reaches the beginning corner, it has finished painting the map with the smallest effort numbers possible. All these little calculations together make sure that the path chosen is as smooth as it can be.

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	Go		TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fpdjsns	C++
	fsq	C++
	halfrost					Go
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM						C#
	trung-hn		Python
	varunu28				Java
	wisdompeak	C++
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
YuriSpiridonov	Python

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