Maximum And Minimun

Question

There are n distinct numbers are given not in sorted order. How much time it will take to select a number say k which is neither k-th minimum nor k-th maximum.

A. O$(n)$

B. O$(1)$

C. O$(k)$

D. O$(k\log k)$.

Comments

Can you give some example?

---

suppose distict numbers are -

3, 4, 9, 5, 8, 2, 6, 10, 1

for k= 3

required number can be any number among {1, 2, 4, 5, 6, 9, 10} .

Am I right ..??

---

K logk ...?

---

please explain ... don't know the ans.

---

Take an example ==> (1,3,-1,-3,2,5,6,7,-5) 

"How much time it will take to select a number say k which is neither k-th minimum nor k-th maximum"

take k = 2 ,which is neither 2nd min nor 2nd min , right ...

Complexity to find k smallest or largest elements in an array by min heap is ==>

1. Make a min heap = O(n)

2. remove K elements = O(k logn) , so, total O(n + k logn) .

Similarly , using max heap = O(n + k logn) to find max. k elements ...

Hence, total will be O(n + klogn) (sry i wrote k logk , as i treated it different question) .

Space complexity is higher, as we need 2 heaps now .

---

http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/

---

its a different question...

---

Thanks @Kapil..  

.is there any efficient algo than this one possible ??

---

i did thought about O(k) and O(k logk) , but it is not possible . Guess , it will be done only in O(n) ....

---

What about this kapil-

Take any 2k+1 elements and sort it and take middle element of it  ??

---

okkk. take k = 1 in my example array ,

then 2k + 1 = 3 elements

take any 3 elements - 1,6,7

sorting takes O(k log k ) , right....

we have 1,6,7 (1  is minmum here....)

Also, take k = 7

then 15 elements will be there and exceeding array size , so it takes all the elements , which has worst case O(nlgn)

---

we have 1,6,7 1isminmumhere....

Did not get above one ... I think if we take middle of above then we get 6 which is neither kth maximumnor kth min, where k=1.

Also, take k = 7

then 15 elements will be there and exceeding array size , so it takes all the elements , which has worst case Onlgn

For this exception, I had assumed that here n is exponentially large in comparison to k.

And even if we take k= n, then also we can right time complexity as O(k logk) right ..

And we can resolve all exception case 

like.. if total number n < 2k+1, then also just sort it and take 1st or last number as required number(k!=1 .. right ?? 

---

@vijay, if we choose a number say 2 , then it should bot be the 2nd minimum and 2nd maximum , right??

i think this is asked in the question.

---

@Kapil, yes.

So, what should be min time complexity ??

I think it should be O(klog k) ...

What do you say ?

---

yes, i think so O(k logk) is sufficient , but we should really confirm this from arjun sir...

plz, Ask him in the chat box :)

---

can u plz explain k-th min and k-th max means. i'm nt getting.

---

take k = 3,

then the choosen element should not be 3rd min and max,

but it can be 1st/2nd min and max .

---

O(k) I think.

Answer 1

For this algorithm we have two cases$\Rightarrow$

case 1$\Rightarrow$when k$\geq$n

example$\Rightarrow ar\left [ 5 \right ]=\left \{ 5,4,3,2,1 \right \}$

Let $P\left ( x \right )=$Neither 5th Maximum nor 5th minimum .

$\Rightarrow$$\exists {\left ( P\left ( x \right )\right )}'$$\Rightarrow \Theta \left ( 1 \right )$

case 2:when k$< n$

step 1$\Rightarrow$Choose any subset of size $2k+1$

step 2$\Rightarrow$sort the Array $\Rightarrow \Theta \left ( k\log k \right )$

step 3$\Rightarrow$find the median ,it will be neither kth maximum nor kth minimum 

time complexity $T\left ( n \right )= k\log k$

example-:

https://gateoverflow.in/8113/gate2015-2_22 here k$< n$

so median can be found in $\Theta \left ( k \right )$

$T\left ( n \right )=\Theta \left ( k+k\log k \right )= \Theta \left ( k\log k \right )$

Comments

yes in the first case check if k>n,then simply return.i.e no such element exists which is neither kth maximum nor kth minimum

---

@sourav anand

If you take any 2k + 1 elements and find its median, then itself it is neither the kth minimum nor maximum .

Finding median gives O(K) which is more optimal than sorting O(k lg k).

But, there are some drawbacks as it only good for 2k + 1 < N , what if 2k + 1 > N.

Then , finding median gives O(K) still, but actually it now covers the whole array , so it becomes O(N).

Hence, the question has 2 cases and some additional information must be given regarding this.

---

No, now you have the complete input N , and finding a median in this is O(N).