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.

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

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.