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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+18 votes

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.

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

+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

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.

+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

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(n^{2})

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) 1^{s}^{t }smallest element will definitely be at A[0][0] , so print it.

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

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

So, now, we have to compare A[1][0] with other elements to find 3^{rd} 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 1^{st} 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, 3^{rd} smallest element can be in 2^{nd} row ,3^{rd }row, ......n^{th }row...

So, to find 3^{rd} smallest element , apply binary search on 2^{nd} row ,3^{rd }row, ......n^{th }row using above procedure...

So , In the end we will find 3^{rd} 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

@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/4^{th }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 ?..

+7 votes

If all elements are distinct we have to check 1st row and 1st column.So complexity will be O(n^{2})

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)

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

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

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 ?

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?

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.

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.

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.1k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.1k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 1k
- Others 1.3k
- Admissions 447
- Exam Queries 428
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 8

35,487 questions

42,747 answers

121,459 comments

42,138 users