Formatted question description: https://leetcode.ca/all/1102.html
1102. Path With Maximum Minimum Value
Level
Medium
Description
Given a matrix of integers A with R rows and C columns, find the maximum score of a path starting at [0,0] and ending at [R-1,C-1].
The score of a path is the minimum value in that path. For example, the value of the path 8 → 4 → 5 → 9 is 4.
A path moves some number of times from one visited cell to any neighbouring unvisited cell in one of the 4 cardinal directions (north, east, west, south).
Example 1:
Input: [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
Explanation: The path with the maximum score is highlighted in yellow.
Example 2:
Input: [[2,2,1,2,2,2],[1,2,2,2,1,2]]
Output: 2
Example 3:
Input: [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]
Output: 3
Note:
1 <= R, C <= 1000 <= A[i][j] <= 10^9
Solution
For each cell in the matrix, store its row, column and score in the path, where score in the path is the minimum value in the path. Use a priority queue to store the cells, where the cell with the maximum score is polled first. Each time poll a cell from the priority queue, and update its adjacent cells’ scores. Make sure that each cell is visited only once. Since a priority queue is used, it is guaranteed that each cell’s score is the maximum possible score. Finally, return the score at the bottom right corner.
class Solution {
public int maximumMinimumPath(int[][] A) {
final int WHITE = 0;
final int GRAY = 1;
final int BLACK = 2;
int rows = A.length, columns = A[0].length;
int[][] colors = new int[rows][columns];
int[][] values = new int[rows][columns];
int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] array1, int[] array2) {
if (array1[2] != array2[2])
return array2[2] - array1[2];
else if (array1[0] != array2[0])
return array1[0] - array2[0];
else
return array1[1] - array2[1];
}
});
colors[0][0] = GRAY;
values[0][0] = A[0][0];
priorityQueue.offer(new int[]{0, 0, values[0][0]});
while (!priorityQueue.isEmpty()) {
int[] cell = priorityQueue.poll();
int row = cell[0], column = cell[1], value = cell[2];
for (int[] direction : directions) {
int newRow = row + direction[0], newColumn = column + direction[1];
if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && colors[newRow][newColumn] == WHITE) {
colors[newRow][newColumn] = GRAY;
values[newRow][newColumn] = Math.min(value, A[newRow][newColumn]);
priorityQueue.offer(new int[]{newRow, newColumn, values[newRow][newColumn]});
}
}
colors[row][column] = BLACK;
}
return values[rows - 1][columns - 1];
}
}