# Problem Link

**Author:** Aleksa Plavsic

**Tester:** Mark Mikhno

**Editorialist:** Bhuvnesh Jain

# Difficulty

MEDIUM-HARD

# Prerequisites

Binary Search

# Problem

You are given a matrix with of size N * N. Each row and column is either sorted in increasing or decreasing order and all the numbers in the matrix are distinct. You can ask ask at most K questions of the form (i, j) where you get the output as A[i][j], the element at that position in the matrix. You need to find where does the element W exist in the matrix and it doesn’t exist, output -1.

# Explanation

The first 2 subtasks can be easily solved with binary search. For this, simply query the first and last element of each row. This indicates whether the row is sorted in increasing or decreasing order. Now, simply binary search over the elements in every row. This takes at most (ceil(\log{N}) + 2) operations for every row. You can optimize this a bit more by applying binary search for rows for which the W already lies in the range for the initial 2 elements asked for that row.

To proceed towards the full solution, let us first understand a bit more about the structure of the matrix. we have the following theorems:

- Let say we denote increasing columns by U and decreasing columns by V. If two consecutive columns differ have different type i.e. U and V, then there is a change in the type of columns. If this change occurs more than once then all the rows must be either increasing or decreasing. The same applies to the case of rows as well.

**Proof**

Let us consider a 3 X 3 matrix as below:

Since there occurs a change in the type of columns more than once, we assume columns are U V U i.e.

- a < d < i
- b > e > j
- c < f < k.

To show all rows should be either increasing or decreasing, consider the case when row 1 is increasing. This means a < b < c. Assume on the contrary that row 2 is decreasing. So, we have b > f > e > a. This is a contradiction to claim that row 1 in increasing.

If row 3 was decreasing, then we have b > j > k > c, which is again a contradiction to fact that row 1 is increasing. Thus, if row 1 is increasing all rows must be increasing. Similarly, we can prove for the case for decreasing row 1.

The other case of columns being V U V can be proved on similar terms.

Using the proof idea for a matrix 3 X 3, we can extend the idea to higher dimensions and consider smaller 3 X 3 matrices in them (either consider continuous same type columns/rows as a block) to show either all rows/columns will be increasing.

- If all the rows or columns are not of the same type then the matrix is of the special type, which is extended from a 2 X 2 matrix.

The idea for this is based on the above prove which required a matrix of size atleast 3 X 3 as we needed atleast two changes in column/row types. Let us consider a 2 X 2 matrix.

All 16 possibilities are there: (Construct examples on your own for better understanding)

- a < b, c < d, a > c, b > d.
- a < b, c < d, a > c, b < d.
- a < b, c < d, a < c, b > d.
- a < b, c < d, a < c, b < d.

and so on …

We simply extend this 2 X 2 matrix to a N X N matrix where there is exactly one change in the row and column types. The idea is as follows

But while extending from 2 X 2 to N X N matrix, we have only two possibilities. Either both row 1 and column 1 are increasing or both are decreasing. They can’t have the different type. The proof (using 4 X 4 matrix) is below:

Assume row 1 is decreasing and column 1 is decreasing. The type of row and column both changes at 2. So, the row types are (V, V, U, U) and column types are (U, U, V, V).

Using the types of rows and columns, we have a_7 < a_6 < a_5 < a_9 < a_{10} < a_{11}. But it is a contradiction to fact that a_7 > a_{11} as column 3 is decreasing. Thus, the proof is done. (The main idea of the proof is to start moving from an element in increasing direction till you reach one for which result is known and you get a contradiction. This helps us to extend it for N X N matrix as well).

So, there are only 3 types of matrices possible if all the rows and columns are sorted in some order. Great, this also gives some ideas on how to create test cases as well. (If you didn’t get it, try again after reading the above proofs).

To proceed further, we need to intelligently find the type of every row and column in the minimum number of queries. The minimum number cannot be less than 2 * N as for every row we need to query atleast 2 elements to determine its type. But if these 2 * N queries are done intelligently then we can know the type of columns as well. Below is two such technique.

Remember, we have used 2 * N queries till now.

Now, I will describe how to deal with different matrices.

**Case 1: All rows are increasing or decreasing**

Let us iterate the columns from left to right and group them by their type, i.e. considering all consecutive increasing/decreasing columns together. Based on whether columns are increasing or decreasing, select the row. It can be either row 1 or N. If for that row and column range, the numbers have W in their range, we have found a valid sub-rectangle which is the possible candidate to contain W. Note that since we are iterating over columns in increasing order and not doing a binary search. So, if the previous columns were ignored, it means their value was either less or greater than W. So, only the other condition is required to be checked.

Thus, we find a suitable sub-rectangle in which all rows and columns are of the same type and it is the possible candidate to contain W. We use N queries in this step in the worst case. The further solution will be explained later.

**Case 2: All columns are increasing or decreasing**

This is similar to the case 1 and is left as an exercise.

**Case 3: All rows and columns change their type exactly once**

For this, consider the above image shown. We will query the points a, b, c, d first. This will help us determine the type of every four sub-rectangles highlighted. I will show some cases on how to proceed further. (Rest is left as an exercise or can be looked by in the solution)

Assume, both row 1 and column 1 are increasing. This means both a and d will be the largest element in their sub-rectangle. If value W is greater than it, then we can safely ignore such sub-rectangles. If value W is less than a, then we can ignore the sub-rectangles containing b and c as we sub-rectangle containing a might contain W and since rows and columns are increasing, the other 2 sub-rectangles already exceed in values as compared to W. Other cases can be handled similarly.

So, after this process as well, we get at most 2 candidate sub-rectangles which can contain W. Both of them have the property that all rows and columns are either increasing or decreasing.

Thus, in all the above cases, we have a sub-rectangle to query such that all rows and columns in it are either increasing or decreasing. Using the above property, ask at most N questions to find if W exists or not. The strategy for this is explained in the solution. Please refer to the function SolveSubRectangle for more details.

**Last caveat:**

For the cases 1 and 2 the questions asked were 2 * N + N + N, where initial is for determining the type, then for finding sub-rectangle and then solving sub-rectangle.

For the case 3, the questions asked were 2 * N + 4 + N + N, where initial is for determining the type, next 4 for a, b, c, d and last are for at most two candidate sub-rectangles which could be queried. For removing the above additional 4 queries, you can see that it will always be one of the cells which was already queried (see the algorithm for subrectangle and the idea of almost greatest element in solution). So, we need to ask a question for the cell if it was not asked before.

The solution is complete now and the complexity is O(K) as for each query we perform O(1) operation and also know which next cell to query in O(1).

The space complexity is O(N^2) to store the elements of the matrix.

For details, refer to the commented solution of the author (The original solution was written in his native language. I have translated it and added comments for help).

If your approach was somewhat different, please share it in the comments section below, but **with proof on the number of queries**.

# Time Complexity

O(K)

# Space Complexity

O(N^2)

# SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.