LC: Path With Maximum Minimum Value - spiralgo/algorithms GitHub Wiki

Path With Maximum Minimum Value

The Essence:

An interpretation is: The problem is about finding the largest number in some range that satisfies the condition that: There is some path between the start and the end such that the minimum value is that value.

The range aspect is important here. This is basically a search range, and is equal to [0, min(start value, end value)].

Details:

From this, one can binary search this range to find the sought value. For checking if the value satisfies being some minimum value on some path, the grid can be traversed with this value as being the limit, no lesser value being visited.

Other approaches utilizing Union-find and priority queues are also possible.