##### Updated on April 3, 2019

## Problem

Given a matrix of integers, there are many paths to take from the top left to the bottom right. For each path, the smallest number in the path is the

minof the path. Of all theminpaths, find the maximumminpath.

**Examples**:

```
[8, 4, 7]
[6, 5, 9]
There are 3 paths that can be taken from (0, 0) to (2, 1)
8-4-7-9 min: 4
8-4-5-9 min: 4
8-6-5-9 min: 5
The greatest min path is 5.
```

## Input

`M`

- a 2D matrix composed of integers

## Approach

The brute force approach is to recursively traverse down and right from a block in the matrix, and record the minimum as you go along. When you hit the bottom-right of the matrix, you can then update the result with the minimum *only if* the result is smaller than this minimum.

## Solution

```
def find_max_min_path(M):
n = len(M)
m = len(M[0])
result = -float('inf')
def _find_max_min(i, j, min_so_far):
if i >= m or j >= n:
return
curr_min = min(M[j][i], min_so_far)
nonlocal result
if i == m-1 and j == n-1:
result = max(result, curr_min)
return
_find_max_min(i+1, j, curr_min)
_find_max_min(i, j+1, curr_min)
_find_max_min(0, 0, float('inf'))
return result
```

## Solution (Optimized)

An optimization is to use dynamic programming, as the previous solution will repeatedly visit blocks that were visited before.

The basic intuition for the dynamic programming approach is that we create another 2D matrix `dp`

(same size as the original input) and as we walk through the matrix `M`

, we cache the results into `dp`

.

Each block in `dp`

has the maximum min path value.

\(dp[j][i]\) is the minimum of two things:

- The maximum of the entry right before it: (\(i-1\) or \(j-1\))
- The current value at \(M[j][i]\)

```
def find_max_min_dp(M):
n = len(M)
m = len(M[0])
dp = [[0] * m for _ in range(n)]
dp[0][0] = M[0][0]
for i in range(1, m):
dp[0][i] = min(M[0][i], dp[0][i-1])
for j in range(1, n):
dp[j][0] = min(M[j][0], dp[j-1][0])
for i in range(1, m):
for j in range(1, n):
dp[j][i] = min(max(dp[j-1][i], dp[j][i-1]), M[j][i])
return dp[n-1][m-1]
```