Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Path With Minimum Effort (medium)
On this page

Problem Statement

Examples

Try it yourself

Problem Statement

You are given a 2D array heights[][] of size n x m, where heights[n][m] represents the height of the cell (n, m).

Find a path from the top-left corner to the bottom-right corner that minimizes the effort required to travel between consecutive points, where effort is defined as the absolute difference in height between two points. In a single step, you can either move up, down, left or right.

Return the minimum effort required for any path from the first point to the last.

Examples

Example 1:

  • Input: heights =
 [[1,2,3],
  [3,8,4],
  [5,3,5]]
  • Expected Output: 1
  • Justification: The path with the minimum effort is along the edges of the grid (right, right, down, down) which requires an effort of 1 between each pair of points.

Example 2:

  • Input: heights =
[[1,2,2],
 [3,3,3],
 [5,3,1]]
  • Expected Output: 2
  • Justification: The path that minimizes the maximum effort goes through (1,2,2,3,1), which has a maximum effort of 2 (from 3 to 1).

Example 3:

  • Input: heights =
[[1,1,1],
 [1,1,1],
 [1,1,1]]
  • Expected Output: 0
  • Justification: The path that minimizes the maximum effort goes through (1,1,1,1,1), which has a maximum effort of 0.

Constraints:

  • rows == heights.length
  • columns == heights[i].length
  • 1 <= rows, columns <= 100
  • 1 <= heights[i][j] <= 10<sup>6</sup>

Constraints:

  • rows == heights.length
  • columns == heights[i].length
  • 1 <= rows, columns <= 100
  • 1 <= heights[i][j] <= 10<sup>6</sup>

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

On this page

Problem Statement

Examples

Try it yourself