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.
Flowchart Walkthrough
Let's analyze LeetCode 1102. Path With Maximum Minimum Value using the Flowchart. Here’s a step-by-step walkthrough:
Is it a graph?
- Yes: Each cell in the grid can be considered as a node, and edges exist between adjacent cells.
Is it a tree?
- No: The graph is not necessarily a hierarchy with a single root, as multiple paths are possible between various nodes.
Is the problem related to directed acyclic graphs (DAGs)?
- No: The relationships between cells are bidirectional without involving directed acyclical edges.
Is the problem related to shortest paths?
- Yes: We aim to maximize the minimum value along any path from the top-left corner to the bottom-right corner, which implies evaluating paths to determine the optimal one.
Is the graph weighted?
- Yes: Despite not having explicit weights, each cell value can be treated as a weight since the objective involves maximizing the path's minimum cell value.
Since we've identified the situation involving the shortest path in a weighted scenario using DFS:
Conclusion: The flowchart implies considering Depth-First Search (DFS) due to the need for exploring paths in a weighted grid, focusing on achieving the maximum minimum value across all possible paths.
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:
-
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.
-
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.
-
Initialize a Disjoint Set Union (DSU) data structure, which initially treats every cell as an isolated component.
-
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.
-
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. -
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.
Learn more about Depth-First Search, Breadth-First Search, Union Find and Heap (Priority Queue) patterns.
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:
-
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)]
-
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()
-
Initialize the Union-Find structure
p
where each element is its own parent:1p = list(range(m * n))
-
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]
-
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()
-
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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.
Solution Implementation
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
25 answer = 0
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()
37 answer = value # Update answer to the current value
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
52 return answer
53
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
37 // Explore adjacent cells.
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
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
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.
-
Creating the list
q
takesO(m * n)
time since it involves iterating over all elements in the grid once. -
Sorting the list
q
has a time complexity ofO(m * n * log(m * n))
becauseq
containsm * n
elements. -
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 listq
. For each element, it performs afind
operation for the current cell and potentially for its neighbors. As per the path compression infind
and union by rank optimizations (not explicitly shown in the code given but commonly associated with this pattern), the amortized time complexity of eachfind
can be consideredO(α(m * n))
, whereα
is the inverse Ackermann function, which grows very slowly and can be considered almost constant for all practical purposes. -
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
.
-
The list
q
storesm * n
tuples, which means its space complexity isO(m * n)
. -
The list
p
also storesm * n
parent indices, contributing anotherO(m * n)
to the space complexity. -
The
vis
set stores a pair of integers for each visited cell. In the worst case, all cells are visited, which means thevis
set can grow toO(m * n)
.
Considering these data structures, the space complexity of the code is O(m * n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a good use case for backtracking?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.