All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Micro and Matrix
Tag(s):

Algorithms, Dynamic Programming, Medium

Problem
Editorial
Analytics

In Micro's class, students sit in a matrix of $$N$$ rows and $$N$$ columns, both numbered from $$1$$ to $$N$$. Each student is having an I.Q. level, which is an integer value. It's history class right now and Micro is getting really bored. So, he started wondering about an interesting problem. He wants to find out the largest number $$X$$, such that there is a submatrix of size $$X \times X$$ in which all students have same I.Q. level. Please help Micro to find out the answer.

Input:
First line consists of a single integer $$T$$ denoting the number of test cases.
First line of each test case consists of a single integer denoting $$N$$.
Each of the following $$N$$ lines consists of $$N$$ space separated integers. $$j^{th}$$ integer in $$i^{th}$$ row denotes the I.Q. level of the student sitting on $$j^{th}$$ chair of $$i^{th}$$ row.

Output:
For each test case print the largest possible value of $$X$$ in a new line.

Constraints:
$$1 \le T \le 10 $$
$$1 \le N \le 1000$$
$$1 \le A[i][j] \le 10^9, A[i][j] = $$ I.Q. level of the student sitting on $$j^{th}$$ chair of $$i^{th}$$ row.

Note: Please use fast I/O methods.

SAMPLE INPUT
1
3
2 2 3
2 2 3
3 3 3
SAMPLE OUTPUT
2
Explanation

Biggest square submatrix with all elements having equal value is the one with top-left corner $$(1,1)$$ and bottom-right corner $$(2,2)$$.

Time Limit: 2.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: 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, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

March Easy '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications