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.

0

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

+15 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]$. S,o 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.

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

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

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]

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.

+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.4k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,058 questions

45,554 answers

131,891 comments

48,911 users