Reference: LeetCode

Difficulty: Medium

## Problem

Given a matrix of integers A with

`R`

rows and`C`

columns, find themaximum scoreof a path starting at`[0, 0]`

and ending at`[R-1, C-1]`

.

The score of a path is the

minimum valuein that path. For example, the value of the path`8 → 4 → 5 → 9`

is`4`

.

A path moves some number of times from one visited cell to any neighbouring unvisited cell in one of the

`4`

cardinal directions (north, east, west, south).

**Note:**

- 1 <=
`R`

,`C`

<= 100 - 0 <=
`A[i][j]`

<= 10^9

**Example:**

1 | Input: [[5,4,5],[1,2,6],[7,4,6]] |

## Analysis

### Backtracking

Here is the code of backtracking `Time Limit Exceeded`

.

1 | public int maximumMinimumPath(int[][] A) { |

**Time:** $O(4^{RC})$**Space:** $O(RC)$

### Priority Queue

Use a max heap. Consider the following example.

1 | 6 8 5 |

Notice that in the above example it stops expanding at `5 -> 4`

since there is a better way to go.

**Note:**

- Learn how to write the comparator.
- Learn how to manage four-direction traversal.

1 | public int maximumMinimumPath(int[][] A) { |

**Time:** $O(RC \log{(RC)})$**Space:** $O(RC)$

## Two-Direction Version

Given a matrix with

`r`

rows and`c`

columns, find the maximum score of a path starting at`[0, 0]`

and ending at`[r - 1, c - 1]`

. The score of a path is the minimum value in that path. For example, the score of the path`8 → 4 → 5 → 9`

is`4`

.

**Don’t include the first or final entry. You can only move either down or right at any point in time.**

Playground: https://leetcode.com/playground/sbkFjCbE

### DP

Define: `dp[i][j]`

is the max score from `[0][0]`

to `[i][j]`

Recurrence: `dp[i][j]`

= max( min(`dp[i-1][j]`

, `grid[i][j]`

), min(`dp[i][j-1])`

, `grid[i][j]`

)

1 | // "static void main" must be defined in a public class. |

#### DP (2D)

1 | // DP (2D) |

**Time:** $O(rc)$**Space:** $O(rc)$

#### DP (1D)

1 | // DP (One Row or Column) |

**Time:** $O(rc)$**Space:** $O(r)$ or $O(c)$