1102. Path With Maximum Minimum Value

---

My Solution

Solution 1: Linear Search + BFS (Brute Force, TLE)

The Key Idea for Solving This Coding Question

C++ Code

#define WHITE (0)
#define GRAY  (1)
#define BLACK (2)

struct cell {
    int r;
    int c;
    cell(int r, int c) : r(r), c(c) {}
};

class Solution {
public:
    int maximumMinimumPath(vector<vector<int>> &grid) {
        rows = grid.size();
        cols = grid[0].size();

        int minScore = min(grid[0][0], grid[rows - 1][cols - 1]);
        while (minScore >= 0) {
            if (doesPathExist(grid, minScore)) {
                return minScore;
            } else {
                --minScore;
            }
        }

        return -1;
    }

private:
    int rows;
    int cols;

    bool doesPathExist(vector<vector<int>> &grid, int minScore) {
        vector<vector<int>> state(rows, vector<int>(cols, WHITE));
        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        queue<cell> q;
        bool isMinScoreFound = false;

        q.push(cell(0, 0));
        state[0][0] = GRAY;

        while (!q.empty()) {
            int qLen = q.size();
            for (int i = 0; i < qLen; ++i) {
                cell curr = q.front();
                q.pop();

                if (grid[curr.r][curr.c] == minScore) {
                    isMinScoreFound = true;
                }
                if (isMinScoreFound && ((curr.r == rows - 1) && (curr.c == cols - 1))) {
                    return true;
                }

                for (auto &dir : dirs) {
                    int nextR = curr.r + dir[0], nextC = curr.c + dir[1];
                    if (nextR < 0 || rows <= nextR || nextC < 0 || cols <= nextC ||
                        state[nextR][nextC] != WHITE || grid[nextR][nextC] < minScore) {
                        continue;
                    }
                    state[nextR][nextC] = GRAY;
                    q.push(cell(nextR, nextC));
                }
            }
        }
        return false;
    }
};

Time Complexity

$O(n\cdot m\cdot k)$

$n$ is the number of rows of grid.

$m$ is the number of columns of grid.

$k$ is the possible maximum number in grid.

Space Complexity

$O(n\cdot m)$

$n$ is the number of rows of grid.

$m$ is the number of columns of grid.

Solution 2: Binary Search + BFS

The Key Idea for Solving This Coding Question

C++ Code

#define WHITE (0)
#define GRAY  (1)
#define BLACK (2)

struct cell {
    int r;
    int c;
    cell(int r, int c) : r(r), c(c) {}
};

class Solution {
public:
    int maximumMinimumPath(vector<vector<int>> &grid) {
        rows = grid.size();
        cols = grid[0].size();

        int left = 0, right = min(grid[0][0], grid[rows - 1][cols - 1]);
        while (left < right) {
            int middle = left + (right - left + 1) / 2;
            if (doesPathExist(grid, middle)) {
                left = middle;
            } else {
                right = middle - 1;
            }
        }
        if (doesPathExist(grid, left)) {
            return left;
        }

        return -1;
    }

private:
    int rows;
    int cols;

    bool doesPathExist(vector<vector<int>> &grid, int minScore) {
        vector<vector<int>> state(rows, vector<int>(cols, WHITE));
        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        queue<cell> q;

        q.push(cell(0, 0));
        state[0][0] = GRAY;

        while (!q.empty()) {
            int qLen = q.size();
            for (int i = 0; i < qLen; ++i) {
                cell curr = q.front();
                q.pop();

                if ((curr.r == rows - 1) && (curr.c == cols - 1)) {
                    return true;
                }

                for (auto &dir : dirs) {
                    int nextR = curr.r + dir[0], nextC = curr.c + dir[1];
                    if (nextR < 0 || rows <= nextR || nextC < 0 || cols <= nextC ||
                        state[nextR][nextC] != WHITE || grid[nextR][nextC] < minScore) {
                        continue;
                    }
                    state[nextR][nextC] = GRAY;
                    q.push(cell(nextR, nextC));
                }
            }
        }
        return false;
    }
};

Time Complexity

$O(n\cdot m\cdot logk)$

$n$ is the number of rows of grid.

$m$ is the number of columns of grid.

$k$ is the possible maximum number in grid.

Space Complexity

$O(n\cdot m)$

$n$ is the number of rows of grid.

$m$ is the number of columns of grid.

Solution 2: Binary Search + DFS

The Key Idea for Solving This Coding Question

C++ Code

#define WHITE (0)
#define GRAY  (1)
#define BLACK (2)

struct cell {
    int r;
    int c;
    cell(int r, int c) : r(r), c(c) {}
};

class Solution {
public:
    int maximumMinimumPath(vector<vector<int>> &grid) {
        rows = grid.size();
        cols = grid[0].size();

        
        int left = 0, right = min(grid[0][0], grid[rows - 1][cols - 1]);
        while (left < right) {
            vector<vector<int>> state(rows, vector<int>(cols, WHITE));
            int middle = left + (right - left + 1) / 2;
            if (doesPathExist(grid, 0, 0, state, middle)) {
                left = middle;
            } else {
                right = middle - 1;
            }
        }
        vector<vector<int>> state2(rows, vector<int>(cols, WHITE));
        if (doesPathExist(grid, 0, 0, state2, left)) {
            return left;
        }

        return -1;
    }

private:
    int rows;
    int cols;

    bool doesPathExist(vector<vector<int>> &grid, int r, int c, 
                       vector<vector<int>> &state, int minScore) {
        if (r < 0 || rows <= r || c < 0 || cols <= c || 
            state[r][c] != WHITE || grid[r][c] < minScore) {
            return false;
        }
        if (r == rows - 1 && c == cols - 1) {
            return true;
        }

        state[r][c] = GRAY;
        if (doesPathExist(grid, r - 1, c, state, minScore)) {
            return true;
        }
        if (doesPathExist(grid, r + 1, c, state, minScore)) {
            return true;
        }
        if (doesPathExist(grid, r, c - 1, state, minScore)) {
            return true;
        }
        if (doesPathExist(grid, r, c + 1, state, minScore)) {
            return true;
        }
        state[r][c] = BLACK;

        return false;
    }
};

Time Complexity

$O(n\cdot m\cdot logk)$

$n$ is the number of rows of grid.

$m$ is the number of columns of grid.

$k$ is the possible maximum number in grid.

Space Complexity

$O(n\cdot m)$

$n$ is the number of rows of grid.

$m$ is the number of columns of grid.

Miscellaneous