1102

1102. Path With Maximum Minimum Value (Medium)

Given an m x n integer matrix grid, return the maximum score of a path starting at (0, 0) and ending at (m - 1, n - 1) moving in the 4 cardinal directions.

The score of a path is the minimum value in that path.

• For example, the score of the path 8 → 4 → 5 → 9 is 4.

 

Example 1:

Input: grid = [[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: grid = [[2,2,1,2,2,2],[1,2,2,2,1,2]]
Output: 2

Example 3:

Input: grid = [[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

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• 0 <= grid[i][j] <= 109

Companies:
Google, Facebook, Amazon

Related Topics:
Array, Depth-First Search, Breadth-First Search, Union Find, Heap (Priority Queue), Matrix

Similar Questions:

• Path With Minimum Effort (Medium)

Solution 1. Heap

We use a max heap to do a BFS -- greedily extending towards the path with maximum score.

// OJ: https://leetcode.com/problems/path-with-maximum-minimum-value/
// Author: github.com/lzl124631x
// Time: O(MNlog(MN))
// Space: O(MN)
class Solution {
    typedef array<int, 3> T;
public:
    int maximumMinimumPath(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size(), dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
        priority_queue<T> pq;
        pq.push({A[0][0],0,0});
        A[0][0] = -1;
        while (pq.size()) {
            auto [score, x, y] = pq.top();
            pq.pop();
            if (x == M - 1 && y == N - 1) return score;
            for (auto &[dx, dy] : dirs) {
                int a = x + dx, b = y + dy;
                if (a < 0 || a >= M || b < 0 || b >= N || A[a][b] == -1) continue;
                pq.push({ min(score, A[a][b]), a, b });
                A[a][b] = -1;
            }
        }
        return -1;
    }
};

Solution 2. UnionFind

// OJ: https://leetcode.com/problems/path-with-maximum-minimum-value/
// Author: github.com/lzl124631x
// Time: O(MNlog(MN))
// Space: O(MN)
class UnionFind {
    vector<int> id;
public:
    UnionFind(int n) : id(n) {
        iota(begin(id), end(id), 0);
    }
    int find(int a) {
        return id[a] == a ? a : (id[a] = find(id[a]));
    }
    void connect(int a, int b) {
        id[find(a)] = find(b);
    }
    bool connected(int a, int b) {
        return find(a) == find(b);
    }
};
class Solution {
public:
    int maximumMinimumPath(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size(), dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}, ans = INT_MAX;
        vector<array<int, 2>> pos;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                pos.push_back({i, j});
            }
        }
        sort(begin(pos), end(pos), [&](auto &a, auto &b) { return A[a[0]][a[1]] > A[b[0]][b[1]]; }); // Greedily pick the cells with greatest value first.
        UnionFind uf(M * N);
        for (auto &[x, y] : pos) {
            ans = min(ans, A[x][y]);
            A[x][y] = -1; // Mark A[x][y] = -1 as visited
            for (auto &[dx, dy] : dirs) {
                int a = x + dx, b = y + dy;
                if (a < 0 || b < 0 || a >= M || b >= N || A[a][b] != -1) continue;
                uf.connect(x * N + y, a * N + b); // Connect the current position with a visited neighbor
            }
            if (uf.connected(0, M * N - 1)) return ans; // If (0,0) and (m-1, n-1) are connected, we've found the path
        }
        return -1;
    }
};