# 1102. Path With Maximum Minimum Value

## Problem Description

In this problem, we have a 2-dimensional grid represented by an `m x n` matrix. The goal is to find a path from the top-left corner `(0, 0)` to the bottom-right corner `(m - 1, n - 1)` such that the minimum value encountered on this path is as high as possible. In other words, we are trying to maximize the minimum value. While moving through the grid, we can move in any of the four cardinal directions: up, down, left, or right. The 'score' of a path is defined as the smallest number on that path. For example, if a path goes through the numbers `[8, 4, 5, 9]`, the path's score would be `4`, since that is the smallest number encountered on the path.

The problem asks us to find this maximum score that we can achieve by traveling from the starting point to the ending point under the given constraints.

## Intuition

The intuition behind the solution is to represent the grid as a graph where each cell is connected to its adjacent cells (up, down, left, right). We want to find a path where the minimum value is maximized, which hints towards using a 'max-min' strategy or optimization.

Looking at this problem from a graph perspective, we can use Disjoint Set Union (DSU) to find sets of connected nodes or in our case, cells. By taking advantage of the ability to union disjoint sets and find the root of a set in DSU, we can connect cells one by one in decreasing order of their values. This is because we know that if we start connecting from the highest values, the smallest value we connect at the moment of connecting the start to the end will be the maximum minimum value possible.

Steps in the approach can be broken down as follows:

1. Flat the 2D grid into a 1D list and keep track of each cell's value and its coordinates. This way, we can sort the cells based on their values.

2. Sort all cells in descending order of their values because we need to deal with the biggest numbers first. If we connect a path with high values first, the smallest value of that path is guaranteed to be as large as possible.

3. Initialize a Disjoint Set Union (DSU) data structure, which initially treats every cell as an isolated component.

4. Pop the cells one by one from the sorted list and union their sets if they are adjacent and have already been visited. To track visitation, we use a set.

5. After each union operation, check if the start `(0, 0)` and the end `(m - 1, n - 1)` belong to the same set. If they do, we have found a path where all values are greater or equal to the current cell's value.

6. Keep track of the value of the last cell connected at the moment we unify the start and the end for the first time. At this point, we terminate the process, as any further connections will only involve lower values.

This approach ensures that we will find the maximum score for the path from the top-left to the bottom-right corner of the grid.

## Solution Approach

The solution implements the Union-Find algorithm, also known as the Disjoint Set Union (DSU) algorithm. It involves two primary operations: `find` and `union`. The `find` operation checks which set a particular element belongs to and returns the representative or root of that set. The `union` operation merges two sets into one. If the sets are already joined, it does nothing.

We represent each cell as an element in the DSU. Each element initially points to itself, indicating that they each belong to a distinct set. The code also uses the `find` operation to perform path compression, which is an optimization that flattens the structure of the tree, ensuring that each lookup is quick and efficient by updating the parent reference to point to the root upon each call.

The provided solution highlights these steps using Python code:

1. Flatten the 2D matrix `grid` into a list of tuples, with each tuple containing the value and the coordinates `(i, j)` of a cell. This is seen in the code:

``1q = [(v, i, j) for i, row in enumerate(grid) for j, v in enumerate(row)]``
2. Sort this list of tuples in descending order of their values. Since Python's sort is stable and we do not reverse, we effectively sort in ascending order and later pop elements from the end, mimicking descending order:

``1q.sort()``
3. Initialize the Union-Find structure `p` where each element is its own parent:

``1p = list(range(m * n))``
4. The `find` function is defined as follows, implementing path compression:

``````1def find(x):
2    if p[x] != x:
3        p[x] = find(p[x])
4    return p[x]``````
5. The solution iteratively tries to connect cells with the highest values first. While the start and end are not connected:

``````1while find(0) != find(m * n - 1):
2    v, i, j = q.pop()``````
6. For each cell, it adds the cell to a visited set (`vis`), checks its cardinal neighbors, and if any have been visited, it performs a union operation:

``````1vis.add((i, j))
2for a, b in pairwise(dirs):
3    x, y = i + a, j + b
4    if 0 <= x < m and 0 <= y < n and (x, y) in vis:
5        p[find(x * n + y)] = find(i * n + j)``````

The function `pairwise(dirs)` in the provided code is presumably an iterator that returns consecutive pairs from the `dirs` iterable, which contains offsets to represent the 4 cardinal directions. This function is not inherent to Python's standard libraries, so the implementation likely came from an external module or the author's own definition.

After the loop, when the start and the end cell belong to the same set, the solution has been found. The last value `v` assigned during the final union operation before exiting the loop represents the maximum score of the path. This value is returned as the answer.

๐ช
Level Up Your
Algo Skills

### Example Walkthrough

Let's walk through a small example to illustrate the solution approach with a `3x3` grid.

Suppose our grid is:

``````13 4 5
23 2 5
34 2 1``````

We want to find the path from the top left `(0, 0)` to the bottom right `(2, 2)` that maximizes the minimum value encountered.

Step 1: Flatten the matrix to list of tuples with value and coordinates:

``1[(3, 0, 0), (4, 0, 1), (5, 0, 2), (3, 1, 0), (2, 1, 1), (5, 1, 2), (4, 2, 0), (2, 2, 1), (1, 2, 2)]``

Step 2: Sort the list in ascending order (we will pop from the end):

``1[(1, 2, 2), (2, 1, 1), (2, 2, 1), (3, 0, 0), (3, 1, 0), (4, 0, 1), (4, 2, 0), (5, 0, 2), (5, 1, 2)]``

Step 3: Initialize the Union-Find structure:

``1p = [0, 1, 2, 3, 4, 5, 6, 7, 8]  // each element's parent is itself``

Step 4: Define the `find` function with path compression.

Step 5: Now, we start connecting cells, beginning with the highest values.

We pop `(5, 1, 2)` and `(5, 0, 2)` and join their respective sets (since the grid allows moving right, left, up, and down, we assume the path can occur):

``````1For (5, 1, 2), neighboring cells (1, 2), (0, 2) are not yet visited.
2For (5, 0, 2), neighboring cells (0, 1), (1, 2) are not yet visited.``````

Step 6: Continue popping and joining until the top-left and bottom-right cells are connected:

Next, we pop `(4, 2, 0)`:

``1For (4, 2, 0), no adjacent cells are visited. So, we skip.``

Next item is `(4, 0, 1)`, which connects to `(5, 0, 2)`:

``````1For (4, 0, 1), neighboring cell (0, 2) is visited.
2
3p[4] = 2, Union operation connects index 4 to set at index 2.``````

Continuing, when we pop `(3, 1, 0)`, it can connect to `(4, 2, 0)`:

``1p[3] = 6, Union operation connects index 3 to set at index 6.``

With `(3, 0, 0)`, we join it to `(4, 0, 1)`:

``````1p[0] = 4, which eventually refers to index 2.
2
3Now, (0, 0) is connected to (0, 2).``````

At this point, we have connected the top-left corner `(0, 0)` to a cell `(0, 2)` that is in the same set as the bottom-right corner `(1, 2)`, due to the earlier connections. So, we have found a path.

Since the last connection made was with a value of `3`, this is the minimum value on the path from `(0, 0)` to `(1, 2)`. That makes the "score" of this path `3`, which is the answer we wanted to find.

Since we have now connected the start and the end, and since we are moving in descending order, further connections will only include lower values this was the highest minimum we could achieve, therefore the process can be terminated.

## Python Solution

``````1from typing import List
2
3class Solution:
4    def maximumMinimumPath(self, grid: List[List[int]]) -> int:
5        # Function to find the root of an element
6        def find(parent, x):
7            if parent[x] != x:
8                parent[x] = find(parent, parent[x])
9            return parent[x]
10
11        # Size of the grid
12        rows, cols = len(grid), len(grid[0])
13
14        # Create a parent array for union-find structure
15        parent = list(range(rows * cols))
16
17        # Create a list of cells with their values, row and column indices
18        cells = [(value, row, col) for row, row_content in enumerate(grid) for col, value in enumerate(row_content)]
19
20        # Sort the cells based on their values in descending order
21        # Since we want to maximize the minimum value on the path, we will start with the maximum value
22        cells.sort(reverse=True)
23
24        # Initialize the answer variable
26
27        # Initialize a visited set to keep track of the cells visited
28        visited = set()
29
30        # Possible directions to move (up, right, down, left) represented as pairs
31        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
32
33        # Continue the loop until the first cell (0) and the last cell (rows * cols - 1) are connected
34        while find(parent, 0) != find(parent, rows * cols - 1):
35            # Get the current highest valued cell and its position
36            value, row, col = cells.pop()
38            visited.add((row, col))  # Mark cell as visited
39
40            # Check all four possible directions
41            for delta_row, delta_col in directions:
42                # Calculate new row and column index
43                new_row = row + delta_row
44                new_col = col + delta_col
45
46                # Check if the new cell is within the grid and has been visited
47                if 0 <= new_row < rows and 0 <= new_col < cols and (new_row, new_col) in visited:
48                    # Perform union operation
49                    parent[find(parent, new_row * cols + new_col)] = find(parent, row * cols + col)
50
51        # Return the maximum minimum value that we can obtain from the path
53``````

## Java Solution

``````1class Solution {
2    // Parent array for union find operations.
3    private int[] parent;
4
5    public int maximumMinimumPath(int[][] grid) {
6        int rows = grid.length;
7        int cols = grid[0].length;
8        parent = new int[rows * cols];
9        List<int[]> cells = new ArrayList<>();
10
11        // Initialize union find structure and list of grid cells.
12        for (int i = 0; i < rows; ++i) {
13            for (int j = 0; j < cols; ++j) {
14                cells.add(new int[] {grid[i][j], i, j});
15                parent[i * cols + j] = i * cols + j;
16            }
17        }
18
19        // Sort the cells based on their value in descending order.
20        cells.sort((cell1, cell2) -> cell2[0] - cell1[0]);
21
22        // Visited array to keep track of visited cells.
23        boolean[][] visited = new boolean[rows][cols];
24
25        // Directions for exploring adjacent cells (up, right, down, left)
26        int[] directions = {-1, 0, 1, 0, -1};
27
28        // Variable to store the maximum minimum value in a path.
29        int maxMinValue = 0;
30
31        // Process each cell starting with the highest value until we connect top-left to bottom-right.
32        for (int i = 0; find(0) != find(rows * cols - 1); ++i) {
33            int[] current = cells.get(i);
34            visited[current[1]][current[2]] = true;
35            maxMinValue = current[0];
36
38            for (int k = 0; k < 4; ++k) {
39                int x = current[1] + directions[k];
40                int y = current[2] + directions[k + 1];
41                if (x >= 0 && x < rows && y >= 0 && y < cols && visited[x][y]) {
42                    union(find(x * cols + y), find(current[1] * cols + current[2]));
43                }
44            }
45        }
46        return maxMinValue;
47    }
48
49    // Find operation of union find with path compression.
50    private int find(int x) {
51        if (parent[x] != x) {
52            parent[x] = find(parent[x]);
53        }
54        return parent[x];
55    }
56
57    // Union operation for union find.
58    private void union(int x, int y) {
59        parent[find(x)] = find(y);
60    }
61}
62``````

## C++ Solution

``````1class Solution {
2public:
3    int maximumMinimumPath(vector<vector<int>>& grid) {
4        int rows = grid.size(), cols = grid[0].size();
5        // Queue to store the value and position (row, column)
6        vector<tuple<int, int, int>> elements;
7        // Parent array for Union-Find
8        vector<int> parent(rows * cols);
9        iota(parent.begin(), parent.end(), 0);
10
11        // Populate the queue with all elements from the grid
12        for (int row = 0; row < rows; ++row) {
13            for (int col = 0; col < cols; ++col) {
14                elements.emplace_back(grid[row][col], row, col);
15            }
16        }
17
18        // Find function for Union-Find with path compression
19        function<int(int)> find = [&](int x) {
20            return parent[x] == x ? x : parent[x] = find(parent[x]);
21        };
22
23        // Sort elements in descending order based on their value in the grid
24        sort(elements.begin(), elements.end(), greater<tuple<int, int, int>>());
25
26        // Minimum value in the path that maximizes the minimum value on that path
27        int maxMinValue = 0;
28
29        // Directions for traversal (up, right, down, left)
30        int dirs[5] = {-1, 0, 1, 0, -1};
31        // Visited matrix for keeping track of visited positions
32        bool visited[rows][cols];
33        memset(visited, false, sizeof(visited));
34
35        for (auto& [value, row, col] : elements) {
36            visited[row][col] = true;
37            maxMinValue = value;
38
39            // Connect current position with valid and visited neighbors using Union-Find
40            for (int k = 0; k < 4; ++k) {
41                int nextRow = row + dirs[k], nextCol = col + dirs[k + 1];
42                if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols && visited[nextRow][nextCol]) {
43                    parent[find(nextRow * cols + nextCol)] = find(row * cols + col);
44                }
45            }
46
47            // Check if start and end are connected
48            if (find(0) == find(rows * cols - 1)) {
49                break;
50            }
51        }
52        // Return the maxMinValue found
53        return maxMinValue;
54    }
55};
56``````

## Typescript Solution

``````1// Helper function to create a range of numbers in an array
2const iota = (size: number): number[] =>
3  Array.from({ length: size }, (_, i) => i);
4
5// The maximumMinimumPath function calculates the maximum minimum value
6// on the path from the top-left to the bottom-right of the grid.
7function maximumMinimumPath(grid: number[][]): number {
8  const rows = grid.length;
9  const cols = grid[0].length;
10  // Elements array to store value with its corresponding row and column in grid
11  const elements: [number, number, number][] = [];
12  // Parent array for Union-Find
13  const parent: number[] = iota(rows * cols);
14
15  // Populate the elements array with all values and their positions from the grid
16  for (let row = 0; row < rows; ++row) {
17    for (let col = 0; col < cols; ++col) {
18      elements.push([grid[row][col], row, col]);
19    }
20  }
21
22  // Find function for Union-Find with path compression
23  const find = (x: number): number => {
24    if (parent[x] === x) {
25      return x;
26    } else {
27      parent[x] = find(parent[x]);
28      return parent[x];
29    }
30  };
31
32  // Sort elements in descending order based on their value
33  elements.sort((a, b) => b[0] - a[0]);
34
35  // Maximum value among the minimum values on all possible paths
36  let maxMinValue = 0;
37
38  // Directions for traversal (up, right, down, left)
39  const dirs = [-1, 0, 1, 0, -1];
40  // Visited matrix for keeping track of visited positions
41  const visited: boolean[][] = Array.from({ length: rows }, () =>
42    new Array(cols).fill(false)
43  );
44
45  for (const [value, row, col] of elements) {
46    visited[row][col] = true;
47    maxMinValue = value;
48
49    // Connect current position with valid and visited neighbors using Union-Find
50    for (let k = 0; k < 4; ++k) {
51      const nextRow = row + dirs[k];
52      const nextCol = col + dirs[k + 1];
53      if (
54        nextRow >= 0 &&
55        nextRow < rows &&
56        nextCol >= 0 &&
57        nextCol < cols &&
58        visited[nextRow][nextCol]
59      ) {
60        parent[find(nextRow * cols + nextCol)] = find(row * cols + col);
61      }
62    }
63
64    // Check if the start (0,0) and end (rows-1, cols-1) are connected
65    if (find(0) === find(rows * cols - 1)) {
66      break;
67    }
68  }
69
70  // Return the maximum minimum value found
71  return maxMinValue;
72}
73``````

## Time and Space Complexity

The given code is implementing a maximum minimum path algorithm, which is likely used to find the path from the top-left corner to the bottom-right corner of a grid such that the minimum value along the path is maximized.

Time Complexity:

The main operations that affect time complexity are sorting the list `q` and the disjoint set union-find operations inside the `while` loop.

1. Creating the list `q` takes `O(m * n)` time since it involves iterating over all elements in the grid once.

2. Sorting the list `q` has a time complexity of `O(m * n * log(m * n))` because `q` contains `m * n` elements.

3. The `while` loop runs until the top-left corner is connected to the bottom-right corner in the disjoint set data structure. In the worst case scenario, it may need to go through all the elements in the sorted list `q`. For each element, it performs a `find` operation for the current cell and potentially for its neighbors. As per the path compression in `find` and union by rank optimizations (not explicitly shown in the code given but commonly associated with this pattern), the amortized time complexity of each `find` can be considered `O(ฮฑ(m * n))`, where `ฮฑ` is the inverse Ackermann function, which grows very slowly and can be considered almost constant for all practical purposes.

4. Inside the `while` loop, for each cell `(i, j)`, it checks at most 4 neighbors, so this introduces another factor of 4, but this is a constant factor that does not change the overall time complexity.

After considering these points, the overall time complexity of the algorithm can be approximated as `O(m * n * log(m * n) + m * n * ฮฑ(m * n))`. However, due to the nature of the `ฮฑ` function, the `log` term dominates, so we can simplify this to `O(m * n * log(m * n))`.

Space Complexity:

The main data structures used that influence the space complexity are the list `q`, the parent list `p`, and the visited set `vis`.

1. The list `q` stores `m * n` tuples, which means its space complexity is `O(m * n)`.

2. The list `p` also stores `m * n` parent indices, contributing another `O(m * n)` to the space complexity.

3. The `vis` set stores a pair of integers for each visited cell. In the worst case, all cells are visited, which means the `vis` set can grow to `O(m * n)`.

Considering these data structures, the space complexity of the code is `O(m * n)`.

๐
Become an
Algo Monster

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ
โTA ๐จโ๐ซ