741 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 | 741 views
+1

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
+1
+1

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

+2

@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

0

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

0

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

0

But it did not say

not in non decreasing order

I am not sure if it means the same

0

2____4____8____9
7____11___19___21
9____13___24___27
10____15___25___29  [I have changed bolded entries]

As you said-"So it depends upon from where you got 2nd element.You can draw a decision tree."

In the modified example above A[0][1] has the smallest element, but to get the correct 3rd smallest I have to check all entries corresponding to both "4" & "7" i.e 9,11,8 (3 elements, which is again O(1)), otherwise entries traversed from "4" (which is 2nd smallest element) are 8,11 which  won't give the correct result.

To find 3rd smallest, I think it doesn't depend on the point where 2nd smallest was found.

Correct me if I am wrong.

0
@Mamta, your first column is not in ascending order now.
0

@Sukannya  I forgot that.

Please check again, though my intended question remains the same.

+1
@Mamta, what I think is, we know A[0][0] will be the smallest, then we compare A[0][1] and A[1][0], in your case A[0][1] is smallest, then we increment some count that moves to next element in row and compare A[0][2] and A[1][0], A[1][0] is smallest, then we increment some count to compare the next element in column A[2][0] and compare with A[0][2] and so on. So, I don't think we have to check all the elements in a row ever as always 2 comprisons are sufficient depending upon the decision you take. I mean if min element found in row, move rowwise and again compare else move columnwise and again compare. Does this make sense?
+1
Thanks, girl! I was applying min heap concept there. Now that I have understood this, I must say that we don't even need 2 comparisons to find 3rd smallest,1 comparison would do, I suppose you also meant that only in your explanation and

this --> "as always 2 comparisons are sufficient"  is a typo error :P
0
@Mamta  and @Sukannya, If repetition  of the elements is allowed ie. if non-descending order of the elements is mentioned in the question then time complexity to find the 3rd smallest distinct element should be O(n) in worst case..right ?
0

@Ankit "to find the 3rd smallest distinct element"-- I think following is the worst case which is close to O(n2)

2__4__4__4
4__4__4__4

4__4__4__4
4__4__4__5

If u know anything better, pls share.

0

@Mamta , I think , It should be O(nlogn) using binary search..

If our matrix is of order n*n  :-

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_4_4_4_4_4_5

Now ,

Step 1) 1st smallest element will definitely be at A[0][0] , so print it.

Step 2) 2nd smallest element will either be A[0][1] or A[1][0]

Let , 2nd smallest element is at A[0][1] ..so print it..

So, now, we have to compare A[1][0] with other elements to find 3rd smallest element..

Step 3) Compare A[1][0] and A[0][2]

if both are equal then it means elements are repeated ...So , apply Binary search in 1st row from A[0][2] to A[0][n-1]  and compare each time with A[1][0]...If middle element > A[1][0] , then go to left part and again apply binary search ..we do this until we get an element which is distinct and just greater than A[0][2]...So , In worst case , we will not find any distinct element after doing binary search on whole 1st row...

Now, 3rd smallest element can be in 2nd row ,3rd  row, ......nth row...

So, to find 3rd smallest element  , apply binary search on  2nd row ,3rd  row, ......nth row using above procedure...

So , In the end we will find 3rd smallest element at A[n-1][0]...

So , here we have applied binary search on total 'n' rows...So , Time Complexity will be O(nlogn)..may be we can do better than this after applying binary search on diagonal  elements since these elements should also be in non-descending order..

Please correct me If anything is wrong..

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!

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