1631. Path With Minimum Effort

Problem

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] <= 10^6

Problem Summary

You are preparing to take part in a hiking activity. You are given a two-dimensional rows x columns map heights, where heights[row][col] represents the height of the cell (row, col). Initially, you are at the top-left cell (0, 0), and you hope to go to the bottom-right cell (rows-1, columns-1) (note that the indices start from 0). Each time, you can move in one of four directions: up, down, left, or right. You want to find a path that requires the minimum effort. The effort value of a path is determined by the maximum absolute difference in height between adjacent cells on the path. Please return the minimum effort required to travel from the top-left cell to the bottom-right cell.

Solution Ideas

This problem has exactly the same solution idea as problem 778. In problem 778, we ask for the shortest time to become connected. In this problem, we ask for the minimum effort value along a connected path. Both ask for a minimum value; the only difference is what the two values represent.
Following the idea of problem 778, this problem also has multiple solutions. The first solution is DFS + binary search. First, transform the problem into an equivalent question. The problem asks us to find the minimum effort value, which is also equivalent to asking whether there exists an effort value x such that as long as the allowed effort is greater than or equal to x, the path must be connected. Use binary search to find this critical value. The effort values are ordered, so the conditions for binary search are satisfied here. The problem states that the pillar heights are in [1,10^6], so the effort value must be in the interval [0,10^6-1]. The condition for determining whether to take the middle value is to use DFS or BFS to search whether the points (0,0) and (N-1, N-1) are connected. Time complexity: O(mnlogC), where m and n are the number of rows and columns of the map, respectively, and C is the maximum height of a cell. The maximum value of C is 10^6, so logC is also a very small constant. Space complexity: O(mn).
The second solution is Union-Find. Sort all edges in the graph by weight in ascending order, and add them to the Union-Find one by one. Once adding an edge with weight x makes the top-left corner connected to the bottom-right corner, the minimum effort value has been found. Note that when adding edges, only add the two types of adjacent edges: i-1 and i, j-1 and j. This is because minimum effort means not going back on the path. To reach a node from the four directions up, down, left, and right, it can only come from above and from the left. Coming from below or from the right definitely wastes effort. Time complexity: O(mnlog(mn)), where m and n are the number of rows and columns of the map, respectively, and the number of edges in the graph is O(mn). Space complexity: O(mn), which is the space needed to store all edges and the Union-Find.

Code

package leetcode

import (
	"sort"

	"github.com/halfrost/leetcode-go/template"
)

var dir = [4][2]int{
	{0, 1},
	{1, 0},
	{0, -1},
	{-1, 0},
}

// Solution 1: DFS + binary search
func minimumEffortPath(heights [][]int) int {
	n, m := len(heights), len(heights[0])
	visited := make([][]bool, n)
	for i := range visited {
		visited[i] = make([]bool, m)
	}
	low, high := 0, 1000000
	for low < high {
		threshold := low + (high-low)>>1
		if !hasPath(heights, visited, 0, 0, threshold) {
			low = threshold + 1
		} else {
			high = threshold
		}
		for i := range visited {
			for j := range visited[i] {
				visited[i][j] = false
			}
		}
	}
	return low
}

func hasPath(heights [][]int, visited [][]bool, i, j, threshold int) bool {
	n, m := len(heights), len(heights[0])
	if i == n-1 && j == m-1 {
		return true
	}
	visited[i][j] = true
	res := false
	for _, d := range dir {
		ni, nj := i+d[0], j+d[1]
		if ni < 0 || ni >= n || nj < 0 || nj >= m || visited[ni][nj] || res {
			continue
		}
		diff := abs(heights[i][j] - heights[ni][nj])
		if diff <= threshold && hasPath(heights, visited, ni, nj, threshold) {
			res = true
		}
	}
	return res
}

func abs(a int) int {
	if a < 0 {
		a = -a
	}
	return a
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

// Solution 2: Union-Find
func minimumEffortPath1(heights [][]int) int {
	n, m, edges, uf := len(heights), len(heights[0]), []edge{}, template.UnionFind{}
	uf.Init(n * m)
	for i, row := range heights {
		for j, h := range row {
			id := i*m + j
			if i > 0 {
				edges = append(edges, edge{id - m, id, abs(h - heights[i-1][j])})
			}
			if j > 0 {
				edges = append(edges, edge{id - 1, id, abs(h - heights[i][j-1])})
			}
		}
	}
	sort.Slice(edges, func(i, j int) bool { return edges[i].diff < edges[j].diff })
	for _, e := range edges {
		uf.Union(e.v, e.w)
		if uf.Find(0) == uf.Find(n*m-1) {
			return e.diff
		}
	}
	return 0
}

type edge struct {
	v, w, diff int
}