Author |
Topic: kth largest element from the 2-d array (Read 5364 times) |
|
spur
Newbie
Gender: 
Posts: 47
|
 |
kth largest element from the 2-d array
« on: Feb 10th, 2013, 1:18pm » |
 Quote  Modify
|
Given a 2 D array. The rows and columns are sorted.
Find the kth largest element from the 2-d array.
e,g input array:
1 2 3 25
4 23 20 88
7 82 90 100
8 83 91 101
k=5
output:88
|
|
 IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: kth largest element from the 2-d array
« Reply #1 on: Mar 14th, 2013, 9:13am » |
Quote Modify
|
Remove the largest element from the matrix and create a hole. Now from all the neighbouring elements, find the largest and move it to hole thereby creating another hole. Keep on moving this hole up and left till the smallest element is moved. Repeat this k times.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: kth largest element from the 2-d array
« Reply #2 on: Mar 15th, 2013, 9:59am » |
Quote Modify
|
You don't need to continue moving the hole after you moved x steps left and y steps up and xy>k (x+1)(y+1)>k .
Where k is the number of elements you still need to extract.
|
| « Last Edit: Apr 7th, 2013, 7:42am by Grimbal » |
IP Logged |
|
|
|
Spicyy
Newbie
Posts: 1
|
|
Re: kth largest element from the 2-d array
« Reply #3 on: Apr 5th, 2013, 11:32am » |
Quote Modify
|
I think we has to go till K steps , May be i am wrong 
@Grimbal suppose in a given example we has to find 15th largest element, then according to you we will stop once we fetch 8 and 25 since that time left = 4 and up = 4 so 4*4 > 15 but 2 is still inside the matrix
plz correct me if i am wrong 
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: kth largest element from the 2-d array
« Reply #4 on: Apr 7th, 2013, 7:41am » |
Quote Modify
|
I have to correct my statement,
it is not xy>k but (x+1)(y+1)>k
But you don't fetch 8 and 25 at the same time.
When in the process of moving the hole you moved the 8 right (and the hole is where the 8 was), then you have x=3 and y=0 and (x+1)(y+1) = 4.
By the way, the original example is incorrect, since 20 is found right of a 23
|
| « Last Edit: Apr 7th, 2013, 7:45am by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print