# 1102. Path With Maximum Minimum Value

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:**

![](https://assets.leetcode.com/uploads/2019/04/23/1313_ex1.JPG)

```
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:**

![](https://assets.leetcode.com/uploads/2019/04/23/1313_ex2.JPG)

```
Input: [[2,2,1,2,2,2],[1,2,2,2,1,2]]
Output: 2
```

**Example 3:**

![](https://assets.leetcode.com/uploads/2019/04/23/1313_ex3.JPG)

```
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`

```cpp
// BFS Dijkstra
int maximumMinimumPath(vector<vector<int>>& A) { // time: O(mn * log(mn)); space: O(mn)
    const vector<pair<int, int> > dirs({ {-1, 0}, {1, 0}, {0, -1}, {0, 1} });
    priority_queue<tuple<int, int, int> > pq;
    pq.emplace(A[0][0], 0, 0);
    const int m = A.size(), n = A[0].size();
    int res = A[0][0];
    A[0][0] = -1; // mark as visited
    while (!pq.empty()) {
        auto [a, i, j] = pq.top();
        pq.pop();
        res = min(res, a);
        if (i == m - 1 && j == n - 1) return res; // finish the path
        for (const auto& dir : dirs) {
            int new_i = i + dir.first, new_j = j + dir.second;
            if (new_i < 0 || new_i >= m || new_j < 0 || new_j >= n || A[new_i][new_j] < 0) continue;
            pq.emplace(A[new_i][new_j], new_i, new_j);
            A[new_i][new_j] = -1; // mark as visited
        }
    }
    return -1;
}
```

```cpp
// Binary Search + DFS
bool dfs(const vector<vector<int> >& A, vector<vector<bool> >& visited, const vector<pair<int, int> >& dirs, int val, int i, int j) {
    const int m = A.size(), n = A[0].size();
    if (i == m - 1 && j == n - 1) return true;
    visited[i][j] = true;
    for (const auto& dir : dirs) {
        int new_i = i + dir.first, new_j = j + dir.second;
        if (new_i >= 0 && new_i < m && new_j >= 0 && new_j < n &&
            !visited[new_i][new_j] && A[new_i][new_j] >= val && 
            dfs(A, visited, dirs, val, new_i, new_j)) return true;
    }
    return false;
}
bool check(const vector<vector<int> >& A, const vector<pair<int, int> >& dirs, int val) {
    const int m = A.size(), n = A[0].size();
    vector<vector<bool> > visited(m, vector<bool>(n, false));
    return dfs(A, visited, dirs, val, 0, 0);
}
int maximumMinimumPath(vector<vector<int>>& A) { // // time: O(mn * log(mn)); space: O(mn)
    const vector<pair<int, int> > dirs({ {-1, 0}, {1, 0}, {0, -1}, {0, 1} });
    const int m = A.size(), n = A[0].size();
    set<int> unique_vals;
    int score_ceiling = min(A[0][0], A[m - 1][n - 1]);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (A[i][j] <= score_ceiling) unique_vals.insert(A[i][j]);
        }
    }
    vector<int> vals(unique_vals.begin(), unique_vals.end()); // sorted unique value array
    int l = 0, r = vals.size() - 1, mid = 0;
    while (l <= r) {
        mid = l + (r - l) / 2;
        if (check(A, dirs, vals[mid])) l = mid + 1;
        else r = mid - 1;
    }
    return vals[r];
}
```

```cpp
// Union Find
int find(vector<int>& roots, int i) {
    return roots[i] == i ? i : roots[i] = find(roots, roots[i]);
}
void uni(vector<int>& roots, int x, int y) {
    int r_x = find(roots, x), r_y = find(roots, y);
    if (r_x != r_y) roots[r_y] = r_x;
}
int maximumMinimumPath(vector<vector<int>>& A) { // time: O(mn * log(mn)); space: O(mn)
    const vector<pair<int, int> > dirs({ {-1, 0}, {1, 0}, {0, -1}, {0, 1} });
    const int m = A.size(), n = A[0].size();
    vector<bool> visited(m * n, false);
    vector<int> roots(m * n);
    vector<pair<int, int> > ids(m * n);
    // Initialization of roots vector
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int k = i * n + j;
            roots[k] = k;
            ids[k] = {i, j};
        }
    }
    // sort in descending order
    auto cmp = [&A](const pair<int, int>& id1, const pair<int, int>& id2) {
        return A[id1.first][id1.second] > A[id2.first][id2.second];  
    };
    sort(ids.begin(), ids.end(), cmp);
    for (const auto& id : ids) {
        int i = id.first, j = id.second, k = i * n + j;
        visited[k] = true;
        for (const auto& dir : dirs) {
            int new_i = i + dir.first, new_j = j + dir.second, new_k = new_i * n + new_j;
            if (new_i < 0 || new_i >= m || new_j < 0 || new_j >= n || !visited[new_k]) continue;
            uni(roots, k, new_k);
            if (find(roots, 0) == find(roots, m * n - 1)) return A[i][j];
        }
    }
    return -1;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/graph/1102.-path-with-maximum-minimum-value.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.