find the atleast one row which neither contain the maximum or the minimum element among all the elements present

Given 2D array is given of order N x N . And it is
filled with distinct elements . Now you have to find the atleast one
row which neither contain the maximum or the minimum element among all
the elements present . The runtime complexity should be less than
O(N^2) .

Naive Solution Will Gothrough All The Row & Coulumn & keep track of min , max .finally return the row that doesn't contain the max or min can't we do better ?

So Mathematically Lets Consider a Set S consisting of any three rows R1, R2, and R3, and compute the min and max of the elements in these rows.

Since all elements are distinct, at most one the three rows
will contain minimum (say R1), and at most one row will
contain maximum (say R2). This means R3 contains neither
max, nor min..

formaly We do not need to look at other rows, as inclusion of other
rows in S, will not make R3 contain max or min.

Correctness of Algorithm: Why We are processing only three row its not making things clear ? How we can sure that from N*N matrix ,if max/min won't be in out of any row from 3 row then it won't contains the max/min from N rows ? e.g. Why it will work that a row that does not contains min/max in N*N matrix will definatly be from one of the threes rows only ?

Things That Strikes In Mind is that as we need to find only 1 min & 1 max (tottal two objects) what can be the possibilities ? hey we wants to extract only two objects out of n*n objects ? what don't pprocess only n+1 rows so that if we are able to cover the all test cases , can be sure that it will satisfy the N*N as well ?

so basically our task reduce to iterate over three rows only & Find the minimum and maximum element from the elements By reading 3 rows.so 2 cases possible.

1. Min and Max element belong to 1 row
2. Min and Max belong to 2 rows

As Said Above using Set.

In both the cases we can get the row which do not contain minnimum and
maximum element from the 3 rows read. If that row does not contain
minimum and maximum element from 3 rows, it won't contain maximum and
minimum element from N rows

lets write 6*6 matrix , try to change the position of min/max , try to test it different test cases , you will find our algorithm will work &b thats work efficiently :)

Time Compelxity O(M^2) where M=3 , differ from N
its Important Questuion & All Things that we have done so far.
we are process only 3*3 sub-matrix . so lest say we have given matrix of size N*N . lets define M=3 & N=k+M where K is N-3 or N-M as i have assigned M to value 3 . so tottal time compexlity will be O(M*M) where M=3 Which is Obviously Much less then N*N isn't it . lets say N=1 million then N^2 will be 1 trillion but m^2 willl be 9 only isn't it its awesome reduction in time compelxity :)


writing the code is not big task for this only designing efficient algo matters.

Correct me if any issue with Time Complexity :)