1631. Path With Minimum Effort

Path With Minimum Effort (LeetCode 1631) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Shortest Path (Dijkstra's Algorithm) subpattern.

• NeetCode 250 · #164 of 250 · Advanced Graphs

How to solve Path With Minimum Effort

Path With Minimum Effort is a Dijkstra's Algorithm for Shortest Path problem, part of Graph Traversal Patterns (DFS & BFS). Master Dijkstra's algorithm for finding shortest paths in weighted graphs with non-negative edges.

Work towards the solution in these steps:

1. Consider the grid as a graph, where adjacent cells have an edge with cost of the difference between the cells.
2. If you are given threshold k, check if it is possible to go from (0, 0) to (n-1, m-1) using only edges of ≤ k cost.
3. Binary search the k value.

The reference solution runs in O(m * n * log(m * n)) time and O(m * n) space.

The Path With Minimum Effort solution and editorial walks through the full approach with reference code.

Problem statement

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route's effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the minimum effort required to travel 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 Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells. This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.

Example 2:

Input: heights = [[1,2,3],[3,8,4],[5,3,5]] Output: 1 Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].

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 Explanation: This route does not require any effort.

Constraints:

- rows == heights.length

- columns == heights[i].length

- 1 <= rows, columns <= 100

- 1 <= heights[i][j] <= 106

Topics and companies

Topics: Array, Binary Search, Depth-First Search, Breadth-First Search, Union Find, Heap (Priority Queue), Matrix.

Reported in interviews at Google, Houzz, ByteDance.

How to practise Path With Minimum Effort on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n * log(m * n)) time and O(m * n) space.

Open Path With Minimum Effort in the code editor, or read the Path With Minimum Effort editorial for a worked solution with its approach and complexity analysis.

Where Path With Minimum Effort sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Shortest Path (Dijkstra's Algorithm) subpattern
• The full DSA patterns sheet

Problems related to Path With Minimum Effort

Other problems that use the same Shortest Path (Dijkstra's Algorithm) and Graph Traversal Patterns (DFS & BFS) techniques:

• Find the Safest Path in a Grid — Medium, same subpattern
• Minimum Obstacle Removal to Reach Corner — Hard, same subpattern
• Minimum Time to Visit a Cell In a Grid — Hard, same subpattern
• Minimum Weighted Subgraph With the Required Paths — Hard, same subpattern
• Network Delay Time — Medium, same subpattern
• Number of Ways to Arrive at Destination — Medium, same subpattern

Path With Minimum Effort FAQ