Katkat
Back

Minimize maximum height along a grid path

GoogleSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to adapt shortest-path algorithms, such as Dijkstra's or Binary Search on the answer, to minimize the maximum edge/node weight along a path.

Problem Statement

You are given an N x M grid of integers, where grid[i][j] represents the height of the terrain at that coordinate. You start at (0, 0) and want to reach (N-1, M-1). You can only move to adjacent cells (up, down, left, right).

The "effort" of a path is defined as the maximum absolute difference in height between any two consecutive cells on that path. Your goal is to find a path from (0, 0) to (N-1, M-1) that minimizes this effort.

Function Signature

def min_max_effort(grid: List[List[int]]) -> int:

Constraints

  • 1 (0,1) -> (0,2) -> (1,2) -> (2,2) has heights [1, 2, 2, 2, 5]. The differences are [1, 0, 0, 3], but we look for a path like (0,0) -> (0,1) -> (1,1) -> (1,2) -> (2,2) where max diff is 2.

Example 2: Input: grid = [[1, 2, 3], [3, 8, 4], [5, 3, 5]] Output: 1

Edge Cases

  • A 1x1 grid should return 0.
  • Paths that are forced to pass through very high or very low points.

Hints

Hint 1

Consider this a graph problem where the nodes are grid cells and the weight of an edge between adjacent cells is the absolute difference of their heights.

Hint 2

If you can determine if a path exists with effort at most 'K' using BFS or DFS, you can binary search for the smallest 'K'.

Hint 3

Alternatively, adapt Dijkstra's algorithm where the distance to a node is the minimum effort required to reach it.

Follow-up questions

  • How does the time complexity change if you use Binary Search + BFS versus Dijkstra's algorithm?
  • Could this problem be solved using a Disjoint Set Union (DSU) approach? If so, how would you structure the edges?
  • How would you modify your solution if you were allowed to move diagonally as well?