title: Find largest square submatrix and largest rectangular submatrix in a sorted nxn matrix where the submatrix contains elements between x and y
body: <p>You are given a nxn matrix of integers such that the entries of row are sorted in increasing order from left to right and entries of each column are sorted in increasing order from top to bottom like below.( I have included the matrix as image below)</p>
  
  <p><a href="https://i.stack.imgur.com/u7vKw.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/u7vKw.png" alt="enter image description here"></a></p>
  
  <p>Now given x and y with x &lt; y I need to compute the largest square submatrix which contains numbers greater than x and less than y in O(n) complexity. For example x=7 and y=50, the following 3x3 matrix is the answer.(Included below as image)</p>
  
  <p><a href="https://i.stack.imgur.com/teb0U.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/teb0U.png" alt="enter image description here"></a></p>
  
  <p>Now given x and y with x &lt; y I need to compute the largest square submatrix which contains numbers greater than x and less than y in O(nlogn) complexity. For example x=7 and y=52, the following 3x4 matrix is the answer.(Included below as image)</p>
  
  <p><a href="https://i.stack.imgur.com/CvTNK.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/CvTNK.png" alt="enter image description here"></a></p>
  
  <p>Please help me in solving the questions.</p>