958 views

Let $A$ be an $n \times n$ matrix such that the elements in each row and each column are arranged in ascending order. Draw a decision tree, which finds $1$st, $2$nd and $3$rd smallest elements in minimum number of comparisons.

edited | 958 views
+1

A beautiful question on the same concept,  https://gateoverflow.in/2766/gate1996_14

0

https://gateoverflow.in/2766/gate1996-14 this question should touch first before comming to below question ...this problem nicely explain by Ahwan mishra

This is a two dimensional array of size $4\times4$.
$2$____$5$____$8$____$9$
$4$____$11$___$19$___$21$
$6$____$13$___$24$___$27$
$8$____$15$___$25$___$29$

You can see the elements in each row and each column are arranged in ascending order.
Smallest element: $A[0][0] = 2$
$2$nd Smallest element: $min(A[0][1],A[1][0])= min(5,4)=4$
$3$rd smallest element: Just exclude the element you got as $2$$^{nd} smallest(4). Here, we can compare A[2][0],A[0][1] no need to compare with A[0][2]. S,o it depends upon from where you got 2nd element. You can draw a decision tree. If you got 2$$^{nd}$best from $A[0][1]$ then what to do & if you get from $A[1][0]$ then what to do.

Any way, time complexity is simply $O(1)$.
The elements are in ascending order. Not in non decreasing order. Clearly they are all distinct in a particular row or column.

edited
0
@ankit, I agree with your explanation but how can we do better using diagonal elements?
0

@Sukannya , Since diagonal elements are also in non-descending order..So , if we apply binary search then initially we compare A[1][0] and middle of diagonal elements (let it is x)..So , we compare A[1] [0] and x..if both are same then our working area to search 3rd distinct element will be reduce by quarterly because x will be in the middle of the matrix and it should be greater than above elements of its column and it is also greater than left of its elements in its row..So , we will not consider initial 1/4th  area of matrix..So, every time after binary search we will reduce the working area to search 3rd distinct smallest element..  I m thinking intuitively..may be I am wrong..

+2

Even I thought diagonal elements would save us time.

2_4_4_4_4_4_4

4_4_4_4_4_4_4

4_4_4_4_4_4_4

4_4_4_4_4_4_4

4_4_4_4_4_5_5

4_4_4_4_5_6_6

4_4_4_4_5_6 _6

Here,Using Binary search, I need to find last occurence(lets say,A[i][j]) of "4" amongst the diagonal elements.

Why last occurrence? Because A[i][j] tells us that ith row or jth column were the last ones who had seen "4". A[i+1][j+1] onwards no element can have "4" in the sub-matrix formed(bolded ones).

2_X_X_X_X_X_X

X_4_X_X_X_X_X

X_X_4_X_X_X_X

X_X_X _4_X_X_X

X_X_X_X_4_X_X

X_X_X_X_X_6_6

X_X_X_X_X_6 _6

Now, we'll have to search in all those italics 'X' to get "5"

Why only italics "X"? Because we are sure only about all straight X's to be 4.

Case1.If only straight X's are 4 then 5 is possibly in last 2 columns or last 2 rows only[italics "X"]

Case 2.If all italics & straight X's are 4s and there is no 5 then the answer would be 6,

But to come to a conclusion whether it's 5 or 6 we have to check at least last 2 rows or last 2 columns for sure, O(logn) again.

Concluding to O(logn) overall time complexity.

+1
@Mamta ,Are u saying 5  could be anywhere in "X" positions ..how it could be left of "4" and above "4" since they are sorted in rowwise and columnwise  ?..
+1
@Ankit, My mistake.

Please check edited comment. Its funny, how we have reduced it from O(n2)->O(nlogn)->O(logn) [Now I am not sure even this one is final or what, don't say O(1) :p]
+1
@Mamta , nice explanation...Thank you!
0

@Mamta Satywali, @ ankitgupta.1729 please check this...

2_4_4_4_4_X_X_X_X_X

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

By given matrix, the first smallest element is 2 (A[0][0] directly print)....................O(1)

The second smallest element is 4( either A[0][1] or A[1][0]) so print.......................O(1)

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(ITALICS ones)....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(logn). ...............................................................................overall O(log n)

Case 2: If X=4, then once after BS on diagonal elements, ill re apply BS till i get 6 (since 6 will be 3 rd minimum then) which 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)

So shouldn't it be O(nlogn) in worst case????...Please correct if I am wrong?

0

@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 :)

+1

@Mamta Satywali  ohkay got my mistake with 'k'....thanks for great insight of analysis, Also can you give more clarity on worst case of BS i.e O(K) as you mentioned??, I was familiar with log k complexity as wc no matter if we have duplicates and element is not present.

+1
Ohh! I confused BS with BST. Edited the answer :)

If all elements are distinct we have to check 1st row and 1st column.So complexity will be O(n2)

Here minimum no of comparison could be 1 , because a[0][0] will be minimum always, now we have to check between a[0][1] and a[1][0]

if all elements are not distinct we have to search all elements of the array

So, minimum comparison could be O(1)

0
@srestha can we do like this??

A[0][0] is smallest so delete it and rearrange matrix which takes not more than n comparisions.

after rearranging at A[0][0] next element can be found.

like this way total number of comparisions=3(n)=O(n)
0
(0,0) will be smallest.

First comparison will be in (1,0) and (0,1) indices.

second comparison between (0,2) (1,1) (2,0) indices
0
@srestha dont we need to do any other comparison except between a[0][1] and a[1][0]?

i mean between a[2][0] and a[0][2]there wont be any comparison?if no,pls tell me why..?
0

I think it could also be done with young tableau,rt?

https://gateoverflow.in/8148/gate2015-2_31

but also told it should be done in min no. of comparison

+2
Why u write O($n^2$) ?
We can always find consecutive 3 smallest in O(1) time right ?
a[0][0], a[0][1] and a[1][0] these are 3 smallest in some order. All other elements are either greater or equal to them.
Is it correct ?
0
yes complexity could be less.

But how do u say 3 smallest  could be inside a[0][0] , a[0][1] and a[1][0]?

It also could be in between a[0][0], a[0][1], a[0][2] , rt?
0
@srestha mam

a[0][0] will be first minimum, no doubt in that

But, the 2nd minimum can be found by comparing a[0][1] and a[1][0].

Lets suppose a[0][1] is 2nd minimum then 3rd minimum can be found by comparing a[0][2] and a[1] [0].

And if a[1][0] is 2nd minimum then 3rd minimum can be found by comparing a[2][0] and a[0] [1].

Total Comparisons=2

Each time we are doing only a constant number of comparisons and hence O(1) time complexity.

Can you point out where I am mistaking.
0

if a[0][1] is 2nd min

3rd min could be in a[1][0],or in a[0][2], or a[2][0].

And then u think if n=3 , then all elements of 1st row and 1st column has to be compare. So, I written O(n2)

0
@srestha mam

if a[0][1] is second minimum, then third minimum can be a[0][2] or a[1][0]

but not a[2][0] because a[1][0] will be Anyways less than a[2][0].

May be I am mistaking somewhere :/

1
2