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.

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:

  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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

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.

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.

  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).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?


Recommended Readings


Got a question? Ask the Monster 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.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄