Maximize the minimum value along a grid path

Q: Maximize the minimum value along a grid path

This question evaluates a candidate's competence in graph traversal and path-optimization concepts, emphasizing reasoning about path scores and handling grid-based constraints.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

You are given an m x n integer matrix A. You start at the top-left cell (0,0) and want to reach the bottom-right cell (m-1,n-1) by moving only in 4 directions (up/down/left/right).

For any path, define its score as the minimum value among all cells on that path.

Task: Return the maximum possible path score.

Input

A : m x n matrix of integers

Output

An integer: the maximum achievable path score

Constraints

1 <= m, n <= 300
-10^9 <= A[i][j] <= 10^9

Example

Input:

5 4 5
1 2 6
7 4 6

Output:

Explanation: One optimal path has minimum cell value 4, and no path can achieve a minimum > 4.

Maximize the minimum value along a grid path

Quick Overview

Input

Output

Constraints

Example

Comments (0)