Problem Description

You are given an m x n integer matrix grid. Your task is to find the maximum score of any path from the top-left corner (0, 0) to the bottom-right corner (m - 1, n - 1).

You can move in 4 cardinal directions: up, down, left, or right.

The score of a path is defined as the minimum value among all cells in that path. For example, if you traverse through cells with values 8 → 4 → 5 → 9, the score of this path would be 4 (the minimum value).

Your goal is to find the path that maximizes this minimum value - in other words, you want to find the path where the smallest number you encounter is as large as possible.

The solution uses a clever approach combining sorting and Union-Find. It sorts all cells by their values in descending order, then progressively adds cells from highest to lowest value. As cells are added, they are connected to their already-visited neighbors using Union-Find. The process continues until the start and end positions become connected, at which point the last added cell's value represents the maximum possible minimum value for any path between start and end.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves traversing a 2D grid where each cell can be considered a node, and movements between adjacent cells (up, down, left, right) represent edges. We need to find a path from one node (0,0) to another (m-1, n-1).

Is it a tree?

• No: The grid structure allows multiple paths between nodes and can contain cycles (you can move in 4 directions), so it's not a tree structure.

Is the problem related to directed acyclic graphs?

• No: The grid allows bidirectional movement between cells, and cycles are possible, so it's not a DAG.

Is the problem related to shortest paths?

• No: We're not looking for the shortest path. Instead, we want to maximize the minimum value along the path, which is a different optimization criterion.

Does the problem involve connectivity?

• Yes: We need to determine if and when the start position (0,0) becomes connected to the end position (m-1, n-1) through visited cells. The solution progressively adds cells and checks when these two positions become connected.

Disjoint Set Union

• Yes: The solution uses DSU (Union-Find) to efficiently track and merge connected components as cells are added in descending order of their values.

Conclusion: While the flowchart leads us to DSU (which the solution indeed uses), the problem can also be solved using DFS with binary search or a modified Dijkstra's algorithm. The DSU approach is particularly elegant here because it allows us to process cells from highest to lowest value and find the exact moment when start and end become connected, giving us the maximum possible minimum value.

Intuition

Think about this problem in reverse. Instead of finding a path and calculating its minimum value, what if we start with the highest possible values and work our way down?

Imagine you're building a path by only using cells with values greater than or equal to some threshold k. If you can connect the start to the end using only these high-value cells, then k is a valid answer. The key insight is that the maximum possible k is the answer we're looking for.

Now, how do we find this maximum k efficiently? We can process cells in descending order of their values. Start with the highest value cells and progressively add lower value cells. Each time we add a cell, we check if it connects to any previously added adjacent cells. We keep track of connected components using Union-Find.

The moment we add a cell that causes the start position (0, 0) and end position (m-1, n-1) to become connected, that cell's value is our answer. Why? Because this is the minimum value we had to include to establish connectivity - any higher threshold would leave start and end disconnected.

This approach is like gradually "flooding" the grid with cells from highest to lowest value, watching for when the flood creates a bridge between start and end. The value at which this bridge forms is the maximum minimum value possible for any path.

The Union-Find data structure is perfect here because it efficiently handles:

1. Merging adjacent visited cells into connected components
2. Quickly checking if two positions belong to the same component

This transforms a complex path-finding problem into a simpler connectivity problem solved by processing cells in the right order.

Learn more about Depth-First Search, Breadth-First Search, Union Find, Binary Search and Heap (Priority Queue) patterns.

Solution Approach

The solution implements the sorting + Union-Find approach to find the maximum minimum value path:

1. Data Structure Setup:

• Create a Union-Find parent array p of size m * n where each cell is initially its own parent
• Each cell (i, j) is mapped to a unique index i * n + j in the parent array

2. Prepare and Sort Cells:

• Create a list q containing triplets (v, i, j) for each cell, where v is the cell value and (i, j) are coordinates
• Sort q in ascending order by value (we'll pop from the end to process in descending order)

3. Process Cells in Descending Order:

while find(0) != find(m * n - 1):
    v, i, j = q.pop()  # Get cell with highest unprocessed value
    ans = v            # Update answer to current cell value
    vis.add((i, j))    # Mark cell as visited

4. Connect Adjacent Visited Cells:

• For each newly visited cell, check its 4 adjacent positions using direction vectors dirs = (-1, 0, 1, 0, -1)
• If an adjacent cell (x, y) has already been visited, union the current cell with it:

if (x, y) in vis:
    p[find(i * n + j)] = find(x * n + y)

5. Union-Find Operations:

• The find function uses path compression to efficiently find the root of a component:

def find(x: int) -> int:
    if p[x] != x:
        p[x] = find(p[x])  # Path compression
    return p[x]

6. Termination Condition:

• The loop continues until find(0) != find(m * n - 1) becomes false
• This means the start cell (0, 0) and end cell (m-1, n-1) are now in the same connected component
• The last processed cell value ans is the maximum minimum value for any path

The algorithm cleverly avoids explicit path finding by recognizing that if we can only use cells with values ≥ k, then k is achievable if and only if there exists a connected path using those cells. By processing cells from highest to lowest value, we find the exact threshold where connectivity is established.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this 3×3 grid:

[5, 4, 5]
[1, 6, 1]
[7, 8, 9]

Our goal is to find a path from (0,0) to (2,2) where the minimum value along the path is maximized.

Step 1: Setup

• Create parent array p = [0,1,2,3,4,5,6,7,8] (each cell is its own parent)
• Map positions: (0,0)→0, (0,1)→1, (0,2)→2, (1,0)→3, (1,1)→4, (1,2)→5, (2,0)→6, (2,1)→7, (2,2)→8

Step 2: Create and Sort Cell List Create list of (value, i, j) triplets and sort by value:

Sorted (ascending): [(1,1,0), (1,1,2), (4,0,1), (5,0,0), (5,0,2), (6,1,1), (7,2,0), (8,2,1), (9,2,2)]

We'll process from the end (highest values first).

Step 3: Process Cells in Descending Order

Iteration 1: Pop (9,2,2) - value 9

• Mark (2,2) as visited
• Check neighbors: none visited yet
• Start (0,0) and end (2,2) not connected
• Continue

Iteration 2: Pop (8,2,1) - value 8

• Mark (2,1) as visited
• Check neighbors: (2,2) is visited
• Union them: connect components containing positions 7 and 8
• Start and end still not connected

Iteration 3: Pop (7,2,0) - value 7

• Mark (2,0) as visited
• Check neighbors: (2,1) is visited
• Union them: connect components containing positions 6 and 7
• Now cells (2,0), (2,1), (2,2) are connected
• Start and end still not connected

Iteration 4: Pop (6,1,1) - value 6

• Mark (1,1) as visited
• Check neighbors: (2,1) is visited
• Union them: connect components containing positions 4 and 7
• Now (1,1) connects to the bottom row
• Start and end still not connected

Iteration 5: Pop (5,0,2) - value 5

• Mark (0,2) as visited
• Check neighbors: (1,2) not visited yet
• Start and end still not connected

Iteration 6: Pop (5,0,0) - value 5

• Mark (0,0) as visited (this is our start!)
• Check neighbors: (0,1) not visited, (1,0) not visited
• Start and end still not connected

Iteration 7: Pop (4,0,1) - value 4

• Mark (0,1) as visited
• Check neighbors: (0,0) and (0,2) are visited, (1,1) is visited
• Union (0,1) with (0,0): positions 1 and 0 connected
• Union (0,1) with (0,2): positions 1 and 2 connected
• Union (0,1) with (1,1): positions 1 and 4 connected
• Now find(0) == find(8) - Start and end are connected!
• Answer = 4

The algorithm found that 4 is the maximum minimum value. Indeed, the path (0,0)→(0,1)→(1,1)→(2,1)→(2,2) has values 5→4→6→8→9, with minimum value 4. No path exists where all values are ≥ 5.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n × (log(m × n) + α(m × n)))

The time complexity breaks down as follows:

• Creating the list q with all grid elements takes O(m × n) time
• Sorting the list q containing m × n elements takes O(m × n × log(m × n)) time
• The while loop processes at most m × n elements from the sorted list
• For each element processed, we:
  • Perform union-find operations with find() calls, which take O(α(m × n)) amortized time where α is the inverse Ackermann function
  • Check up to 4 neighboring cells and potentially perform union operations
• The total union-find operations across all iterations contribute O(m × n × α(m × n)) to the complexity
• The dominant term is the sorting operation, giving us O(m × n × log(m × n)), but when combined with the union-find operations throughout the algorithm, the overall complexity becomes O(m × n × (log(m × n) + α(m × n)))

Space Complexity: O(m × n)

The space complexity consists of:

• The parent array p storing m × n elements: O(m × n)
• The list q storing tuples for all m × n grid cells: O(m × n)
• The visited set vis can contain at most m × n coordinate pairs: O(m × n)
• The recursion stack for find() operations: O(log(m × n)) in the average case with path compression
• Overall space complexity is O(m × n)

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

Common Pitfalls

1. Incorrect Union Operation

A critical pitfall is performing the union operation incorrectly by directly connecting nodes instead of their root representatives.

Incorrect Implementation:

# Wrong: Directly connecting nodes without finding roots
parent[row * cols + col] = next_row * cols + next_col

Correct Implementation:

# Right: Connect the root of one component to the root of another
parent[find(row * cols + col)] = find(next_row * cols + next_col)

2. Boundary Check Omission

Failing to validate that adjacent cells are within grid boundaries before checking if they're visited.

Problematic Code:

for i in range(4):
    next_row = row + directions[i]
    next_col = col + directions[i + 1]
    # Missing boundary check!
    if (next_row, next_col) in visited:  # This could check invalid coordinates
        parent[find(row * cols + col)] = find(next_row * cols + next_col)

Fixed Version:

for i in range(4):
    next_row = row + directions[i]
    next_col = col + directions[i + 1]
    # Add boundary validation
    if (0 <= next_row < rows and 0 <= next_col < cols and 
        (next_row, next_col) in visited):
        parent[find(row * cols + col)] = find(next_row * cols + next_col)

3. Processing Order Confusion

Processing cells in ascending order instead of descending order, which would find the minimum maximum value instead of the maximum minimum value.

Wrong Approach:

cells.sort()  # Ascending order
for value, row, col in cells:  # Process from smallest to largest
    # This finds when disconnection happens, not connection

Correct Approach:

cells.sort()  # Sort ascending
while condition:
    value, row, col = cells.pop()  # Pop from end (largest values first)

4. Forgetting Path Compression

Implementing find() without path compression leads to degraded performance from O(α(n)) to O(n) per operation.

Inefficient Version:

def find(x: int) -> int:
    while parent[x] != x:
        x = parent[x]
    return x

Optimized Version:

def find(x: int) -> int:
    if parent[x] != x:
        parent[x] = find(parent[x])  # Path compression
    return parent[x]

5. Misunderstanding the Answer Update

Updating the answer only once at the end or incorrectly tracking the minimum value.

Incorrect:

# Wrong: Using the first or last processed value
return cells[-1][0]  # This would be the smallest value

Correct:

# Right: The answer is the value of the last cell processed 
# before start and end become connected
while find(0) != find(rows * cols - 1):
    value, row, col = cells.pop()
    result = value  # Continuously update with current value