Amazon Online Assessment (OA) - Maximal Minimum Value Path I

Given a 2D integer array, find the maximum score of a path from the upper-left cell to the bottom-right cell. The score of a path is the minimum value in that path.

Notice: the path can only move right and down.

Examples

Example 1:

Input:

1[7,5,3]
2[2,0,9]
3[4,5,9]

Output: 3

Explanation:

Here are some paths from [0,0] to [2,2] and the minimum value on each path:

path: 7->2->4->5->9, minimum value on this path: 2

path: 7->2->0->9->9, minimum value on this path: 0

path: 7->2->0->5->9, minimum value on this path: 0

In the end, the max score (the minimum value) of all the paths is 3.

Try it yourself