The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+16 votes
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.

asked in Algorithms by Veteran (69k points)
edited by | 587 views

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

2 Answers

+14 votes
Best answer

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.

 

answered by Veteran (10.3k points)
edited by
@Bikram Sir please verify.

@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

+7 votes

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)

answered by Veteran (81k points)
@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 :/

Please clarify!


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,593 questions
40,128 answers
114,021 comments
38,389 users