Monk and New Array
Tag(s):

Binary search algorithm, Easy, 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$, element picked from row 2 will become $A$, 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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...

This Problem was Asked in Challenge Name

CodeMonk (Checkpoint - I)

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Arrays
• Data Structures > Arrays
• Data Structures > Stacks
• Math > Number Theory
• Data Structures > Stacks