Practice/Google/Leetcode 1102. Path With Maximum Minimum Value

Leetcode 1102. Path With Maximum Minimum Value

CodingMust

Problem

You are given an m x n grid of integers where each cell contains a non-negative value. Your goal is to find a path from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1) that maximizes the minimum value encountered along the path.

You can move in four directions: up, down, left, or right. You cannot move diagonally or outside the grid boundaries.

Return the maximum possible value of the minimum cell value along any valid path from start to finish.

Requirements

1. Find a path from the top-left to bottom-right cell
2. Among all valid paths, choose the one that maximizes the minimum cell value
3. Movement is restricted to four directions (up, down, left, right)
4. Return the minimum value along the optimal path

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• 0 <= grid[i][j] <= 10^9
• Expected time complexity: O(m * n * log(max_value))

Examples

Example 1:

Input: grid = [[5,4,5],[1,2,6],[7,4,6]] Output: 4 Explanation: The path 5→4→5→6→6 has a minimum value of 4, which is optimal.

Example 2:

Input: grid = [[2,2,1,2,2,2],[1,2,2,2,1,2]] Output: 2 Explanation: The path that avoids cells with value 1 gives us a minimum of 2.

Example 3:

Input: grid = [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7]] Output: 3 Explanation: Going through cells with higher values, the best achievable minimum is 3.