· By John Kavanagh

Path with Minimum Effort in TypeScript: Minimise the Worst Step

A rocky hillside footpath winds above a lake through green vegetation.
Image by Tim Morgan, licensed from Unsplash.

The shortest walk and the easiest walk aren't necessarily the same walk. A route with many gentle steps can be preferable to a short route containing one unpleasant climb. LeetCode's Path With Minimum Effort problem makes that distinction precise: a route's cost is its largest height difference between neighbouring cells.

We want the smallest possible value of that largest difference, travelling from the top‑left cell to the bottom‑right using horizontal and vertical moves. Adding every difference would answer a different question. Counting steps would answer another one. The recurrence needs to preserve the quantity the problem actually measures.

I'll use a priority queue and a Dijkstra‑style search, but the accumulated score is a maximum rather than a sum. The queue machinery is familiar; the reason it remains valid is worth working through before copying it.


A Route Carries Its Worst Step so Far

Suppose we have reached a cell with effort four. Moving across an edge with difference two leaves the effort at four. Moving across an edge with difference seven raises it to seven. Extending a path therefore calculates max(currentEffort, edgeDifference).

For each cell, best records the smallest effort found so far. A candidate replaces that record only if it is strictly smaller. Equal‑effort arrivals don't add useful information because future choices depend only on the current cell and the accumulated maximum.

This is a useful dominance argument. If two routes reach the same cell with efforts three and eight, extending both over the same next edge can never make the route starting at eight better. The smaller effort is enough to represent everything worth retaining at that cell.

The starting cell has effort zero: a path containing no steps has no climb to contribute. All other cells begin at infinity, representing no discovered route. A single‑cell grid therefore returns zero immediately when its start is removed from the queue.


A Complete Priority Queue

The queue below stores a cell number and score. A comparison function decides whether one score has higher priority than another. For this problem, smaller scores come first. Keeping the comparison explicit will also make the difference from my maximum probability walkthrough visible.

type QueueItem = { node: number; score: number };

class PriorityQueue {
  private readonly items: QueueItem[] = [];
  constructor(private readonly better: (a: number, b: number) => boolean) {}

  push = (item: QueueItem): void => {
    this.items.push(item);
    let child = this.items.length - 1;
    while (child > 0) {
      const parent = Math.floor((child - 1) / 2);
      if (!this.better(this.items[child].score, this.items[parent].score)) break;
      [this.items[child], this.items[parent]] = [this.items[parent], this.items[child]];
      child = parent;
    }
  };

  pop = (): QueueItem | undefined => {
    if (this.items.length === 0) return undefined;
    const first = this.items[0];
    const last = this.items.pop()!;
    if (this.items.length > 0) {
      this.items[0] = last;
      let parent = 0;
      while (parent * 2 + 1 < this.items.length) {
        let child = parent * 2 + 1;
        if (child + 1 < this.items.length &&
          this.better(this.items[child + 1].score, this.items[child].score)) child++;
        if (!this.better(this.items[child].score, this.items[parent].score)) break;
        [this.items[parent], this.items[child]] = [this.items[child], this.items[parent]];
        parent = child;
      }
    }
    return first;
  };
}

Pushing repairs the heap upwards from the new leaf. Popping moves the final item to the root and repairs downwards, choosing the better child each time. A one‑element heap needs no repair after the pop. Equal priorities can emerge in either order because the search does not require a stable queue.

This implementation permits multiple entries for the same cell. Instead of locating and modifying an existing heap item when a route improves, it pushes another arrival. That keeps the heap simple, provided the search checks whether an extracted arrival has become stale.


I flatten a cell into row * columns + column. Division and remainder recover its coordinates when we inspect its neighbours. The input is a non‑empty rectangular grid under the problem's constraints, and the function leaves its heights unchanged.

const minimumEffortPath = (heights: number[][]): number => {
  const rows = heights.length;
  const columns = heights[0].length;
  const best = Array<number>(rows * columns).fill(Infinity);
  best[0] = 0;
  const queue = new PriorityQueue((a, b) => a < b);
  queue.push({ node: 0, score: 0 });
  const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let current: QueueItem | undefined;
  while ((current = queue.pop()) !== undefined) {
    const { node, score } = current;
    if (score > best[node]) continue;
    if (node === best.length - 1) return score;
    const row = Math.floor(node / columns);
    const column = node % columns;
    for (const [dr, dc] of directions) {
      const nextRow = row + dr;
      const nextColumn = column + dc;
      if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns) continue;
      const next = nextRow * columns + nextColumn;
      const difference = Math.abs(heights[row][column] - heights[nextRow][nextColumn]);
      const candidate = Math.max(score, difference);
      if (candidate < best[next]) {
        best[next] = candidate;
        queue.push({ node: next, score: candidate });
      }
    }
  }
  return 0;
};

The stale check comes before the destination check. An old queue entry whose score exceeds the current best record no longer represents the best known arrival and can be ignored. A fresh destination arrival can be returned because the priority ordering makes its score final.

Notice that discovering the destination is not enough. Another route still in the queue may reach it with a lower effort. Returning during neighbour expansion would confuse "we have a route" with "we have the best route", a distinction the priority queue exists to manage.


Why the Greedy Extraction is Sound

Extending a route cannot reduce its effort: taking a maximum preserves or increases the current score. Suppose the queue's smallest fresh arrival has effort e, but an undiscovered route could reach that cell with lower effort. Follow that better route from the start until it crosses from already processed cells to an unprocessed cell.

The crossing would have produced a queue candidate with effort no greater than the supposedly better route's total effort. That candidate would have priority over e and would have been processed first. The contradiction establishes that a smallest fresh arrival cannot later be improved.

The argument depends on monotonic extension, not on adding non‑negative weights specifically. Here maximum supplies the same necessary property. It would be a mistake to reuse the proof for an arbitrary scoring function that can improve after extension without checking that property again.


The Locally Gentle Edge Can Still Lose

Consider the grid [[1, 2, 9], [4, 5, 6]]. Starting by moving right crosses a difference of one, which looks attractive. Following the top row then crosses seven. Moving down first crosses three, followed by differences of one and one, so that route's effort is three.

The route through the centre also reaches the destination with effort three. The answer depends on the largest step across the whole route, not on choosing the smallest next edge greedily. Our queue compares accumulated route effort, which is a different decision from sorting only the immediate neighbouring differences.

Adding differences would rank routes by total variation instead. That can be a reasonable hiking metric, but it isn't this exercise's metric. I find it useful to write the scoring expression in words before discussing any named algorithm: minimise the maximum adjacent height change.


An Independent Way to Check the Answer

For a proposed effort limit t, keep only neighbour connections whose height difference is at most t. Then ask whether the destination is reachable. If it is reachable at t, it remains reachable at any larger threshold, because increasing the limit only adds connections.

That gives a second algorithm: binary‑search the threshold and run a reachability search for each candidate. For small test grids, we can simplify further by collecting all distinct edge differences, trying them in order, and returning the first reachable threshold. This makes a good reference because it uses connectivity tests rather than a priority queue or the same relaxation recurrence.

I compare both answers on exhaustive small grids and seeded larger examples. Equal heights, a single row, a single column, an isolated high centre, and routes that require moving back towards an earlier column are useful cases. Restricting moves to only right and down would quietly solve a different problem.


Costs and the Choice of Formulation

With V cells, the four‑neighbour grid has O(V) edges. Each successful relaxation adds a queue entry, and the lazy duplicate approach uses O(V) queue storage here because the number of edges is linear in the number of cells. Heap operations give O(V log V) time and O(V) auxiliary space.

The threshold version takes O(V log H) time when searching an integer height‑difference range of size H, plus O(V) search storage. Neither bound alone establishes which is faster on a particular grid or engine. The heap version directly improves route scores; the threshold version repeatedly asks a simpler yes‑or‑no question.

My Network Delay Time article uses additive distances, and my stop‑limited flights article shows why extra route constraints can require more state. Here one score per cell is sufficient because a smaller accumulated maximum dominates a larger one. That is the part I would prove before reaching for the heap code.


Looking for technical direction?

I support teams that need senior judgement on React, Next.js, headless CMS architecture, performance, migrations, and technical SEO.