Maze maximum

4.3

23 votes
, Algorithms, Binary Search, C++
Problem

You are given a 2-D matrix \(A\) of size \(N \times M\), its elements are integers. We will assume that the rows of the matrix are numbered from top to bottom from \(1\) to \(N\), the columns are numbered from left to right from \(1\) to \(M\). We will denote the element on the intersecting of the \(i\)-th row and the \(j\)-th column as \(A_{i,j}\).

Find the maximum possible value \(X\), such that:

  • There exists at least one row and one column where all the value of all the elements \(\ge X\).

Input format

  • First line contains two space-separated integers \(N, M\) - the number of rows and columns of the matrix.
  • Next \(N\) lines contains \(M\) space-separated integers denoting the matrix.

Output format

Print the value of \(X\).

Constraints

\(1 \le N \times M \le 10^6 \\ 1 \le A_{i, j} \le 10^9\)

 

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

If \(X = 3\), all the elements in row \(3\) and column \(3\) satisfy the given conditions. It can be proved that \(X\) cannot be greater than \(3\).

Editor Image

?