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:

Image text

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:

Image text

Input: [[2,2,1,2,2,2],[1,2,2,2,1,2]]

Output: 2

Example 3:

Image text

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. 1 <= R, C <= 100
  2. 0 <= 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];
    }
}

All Problems

All Solutions