587 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 | 587 views

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

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]$..... So it depends upon from where you got $2$nd 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 by

@ahwan

yes, it is fine,

just one doubt , what you want to say by this statement " The elements are in ascending order. Not in non decreasing order. " here non decreasing means also increasing order right ?

Numbers are said to be in ascending order when they are arranged from the smallest to the largest number so that is increasing order, same meaning is not it ?

@Bikram Sir,
increasing:   1 2 3 4
non decreasing:  1 1 2 3
So by ascending order they mean strictly increasing. Otherwise we have to check more elements. Sometimes we may have to check every element.
https://stackoverflow.com/questions/1963474/is-a-non-decreasing-sequence-increasing

@Ahwan  if elements are repeated .lets say i have a matrix which contains only 3's.So we should return first second and 3rd minimum as 3? I mean if some element is repeated and that is also minimum then we can have first and second/third min as same?

@rahul sharma 5

"The elements are in ascending order (not in non decreasing order) This line clearly say, they are all distinct in a particular row or column."

But it did not say

not in non decreasing order

I am not sure if it means the same

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)

@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) will be smallest.

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

second comparison between (0,2) (1,1) (2,0) indices
@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..?

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

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 ?
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?
@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.

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)

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