Interview Notes Search

This page uses the site's newer layout, so only the problem statement and the section outline survive in the public payload — open the original for the rest.

Graphs

Path With Minimum Effort

medium

DESCRIPTION (inspired by Leetcode.com)

A hiking app needs to find the easiest route across terrain. Given a 2D grid where each cell represents the elevation at that point, find the path from the top-left corner to the bottom-right corner that minimizes the "effort".

The effort of moving between two adjacent cells is the absolute difference in their elevations. The effort of a path is its single hardest step, meaning the largest effort among all the moves you make along the way.

You can move up, down, left, or right from any cell. Return the minimum effort required.

Example 1:

Input:

heights = [[1,10,2], [2,3,3], [3,2,1]]

Output:

1

Explanation: The cliff (10) has a huge elevation difference. Going around via 1→2→3→2→1 avoids it entirely, with each step having effort at most 1.

Example 2:

Input:

heights = [[4,3,2], [2,6,3], [3,2,1]]

Output:

2

Explanation: The center peak (6) would require effort 3 to cross. Going around the top: 4→3→2→3→1 keeps maximum effort at 2.

Explanation

Understanding the Problem

Brute Force: Try Every Path

A Clever Shortcut: Binary Search + BFS

Recognizing the Graph Pattern

Why Modified Dijkstra Works

Walkthrough

Solution