What is the brute force approach and complexity for Path With Minimum Effort?

Walk every route with backtracking; keep the smallest largest-step with time complexity O(4^(R · C)) and space complexity O(R · C).

What is the optimal approach and complexity for Path With Minimum Effort?

Min-heap over cells; a neighbour's effort is max(effort so far, step) with optimal time complexity O(R · C · log(R · C)) and space complexity O(R · C).

How do you identify the pattern for Path With Minimum Effort?

Look for key signals in the prompt: "minimum effort" indicates Minimise a route's score, then take the best route.; "largest absolute difference between consecutive cells" indicates The route's score is a max over its steps, not a sum.; "moving up, down, left or right in a grid" indicates Each cell is a node, and each neighbour is an edge with a cost..

Path With Minimum Effort

Medium·LeetCode #1631 Pro OnlyMedium

LeetCode

Problem Statement

You are given a grid of heights with rows rows and columns columns. You start in the top-left cell and want to reach the bottom-right cell. You may move up, down, left or right.

The effort of a route is the largest height difference between two neighbouring cells on it. Return the smallest effort over all routes.

Write int minimumEffortPath(vector<vector<int>>& heights) inside class Solution.

Input

heights, a rows × columns grid of positive integers.

Output

The smallest effort of any route from the top-left cell to the bottom-right cell.

Example 1

Input: heights = [[1,2,2],[3,8,2],[5,3,5]]

Output: 2

The route 1, 3, 5, 3, 5 has steps 2, 2, 2, 2, so its effort is 2. The route 1, 2, 2, 2, 5 has a step of 3.

Example 2

Input: heights = [[1,2,3],[3,8,4],[5,3,5]]

Output: 1

The route 1, 2, 3, 4, 5 has steps of 1 only.

Example 3

Input: heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]

Output: 0

There is a route through cells that all have height 1, with no step at all.

Constraints

• rows == heights.length
• columns == heights[i].length
• 1 ≤ rows, columns ≤ 100
• 1 ≤ heights[i][j] ≤ 10^6

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“minimum effort”

→ Minimise a route's score, then take the best route.

“largest absolute difference between consecutive cells”

→ The route's score is a max over its steps, not a sum.

“moving up, down, left or right in a grid”

→ Each cell is a node, and each neighbour is an edge with a cost.

Approach Complexity Ladder

Brute Force — try every simple routeO(4^(R · C))O(R · C)

Walk every route with backtracking; keep the smallest largest-step

Better — binary search on the effort + flood fillO(R · C · log H)O(R · C)

Binary search the effort; check each candidate with one BFS over the cells

Optimal — Dijkstra on cells (max instead of +)O(R · C · log(R · C))O(R · C)

Min-heap over cells; a neighbour's effort is max(effort so far, step)

Brute Force Intuition

Walk every simple route from the top-left cell (never entering a cell already on the route). Carry the largest step seen so far along each walk. At the bottom-right cell, keep the smallest value among all routes.

Recognition rule for this sub-pattern:

Min-heap of (distance, node). Skip stale entries; relax neighbours.

Remember this · Shortest Paths (Weighted)

Trigger

Weighted edges, "minimum cost / time / effort", at most K stops, negative weights, all-pairs distances.

Think

Are edge weights non-negative (Dijkstra), limited by stops (Bellman-Ford), or do I need every pair (Floyd)?

Key question

What is a node's "distance", and when is it final?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Shortest Paths (Weighted) translate into production architectures and low-level memory mechanics.

LLD Architecture