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:

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. 1 <= R, C <= 100

2. 0 <= A[i][j] <= 10^9

// 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;
}

// 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];
}

// 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;
}