@meghna Please check following edited matrix given by you, I have just italicised the entries which need to be checked by BS-

**2**_4_4_4_4_*X_X_X_X_6*

4_**4**_4_4_4_*X_X_X_X_6*

4_4_**4**_4_4_*X_X_X_X_6*

4_4_4 _**4**_4_*X_X_X_X_6*

4_4_4_4**_4**_*X_X_X_X_6*

*X_X_X_X_X_***7**_7_7_7_7

*X_X_X_X_X*_*7_***7**_7_7_7

*X_X_X_X_X*_7_7_**7**_7_7

*X_X_X_X_X*_*7_7_7_***7**_8

*X_X_X_X_X_7_7_7_7_***9**

**Talking about distinct third min only-**

Now for 3rd smallest, let say we apply binary search on diagonal elements and reach the position of last occurrence of 4, I will move A[i+1][j+1] onwards since no element can have "4" in the sub-matrix formed. "**The italicised Xs(including the 6s) are the possible 3rd min elements**"....as you mentioned in your answer. So we'll have to search in all those 'X' to get its value. Now 2 cases occur:

Case 1: if X=5, then once after Binary search on diagonal element (log n), ill again apply BS on (i+1)th row and column until we get to 5, say its in k th row and col then

TC=log n + k(**logk**).[**Why klogk? Because I am not interested in elements after kth col when applying BS row-wise in kth row onwards, (similarly for column-wise BS I will consider only first k elements in col) which are part of 7's submatrix, so I will reduce the size of BS array to k**] ...............................................................................overall O(log n)

Case 2: If X=4, then once after BS on diagonal elements,"**Let (k-1)th element in diagonal was found just greater than 4, so we have to check ****the remaining**** K rows and K columns**" ,ill re-apply BS "**first on (k)****th**** row then(k+1)****th**** row and so on which makes O(****klogk****) .....then i'll reapply BS on (k)****th**** col and then on (k+1)****th**** col and so on which again makes O(****klogk****) and very importantly I have now realised that you have to apply BS in both K rows and K columns in Case 1 too and keep the just min obtained from each BS which is compared to next BS's result and so on**" till i get 6 (since 6 will be 3 rd minimum then) which we will take.

~~TC= log n+ (n/2)(log n) {since checking every row/col after last occurrence of 4 till n/2 times here to reach 6)............................................................................................................overall O(~~~~nlogn~~~~)~~

T.C=O(logn)+O(klogk)

** But this in worst case makes k=n/2 thus T.C=O(n/2log(n/2)) or O(nlogn)**

I just talked about the best case back then. Thanks :)