All Tracks Algorithms Searching Binary Search Problem

Monk and New Array
/

Binary search algorithm, Searching algorithm, Sorting, approved

Problem
Editorial
Analytics

Monk has a matrix of size \(N \times M\), and he wants to pick one element from each row to make a new array A of size N. He wants to find the minimum possible value of absolute difference between any two adjacent elements in the array A. Please note that the element picked from row 1, will become \(A[1]\), element picked from row 2 will become \(A[2]\), and so on.

Input:
First line consists of two space separated integers denoting N and M.
Each of the following N lines consists of M space separated integers denoting the matrix \(mat\).

Output:
Print the required answer in a new line.

Constraints:
\(2 \le N, M \le 1000\)
\(1 \le mat[i][j] \le 10^9\)

SAMPLE INPUT
2 2
8 4
6 8
SAMPLE OUTPUT
0
Explanation

Minimum difference Monk can achieve is 0 by choosing 8 from both rows.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?