wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> kth largest element from the 2-d array
        
(Message started by: spur on Feb 10^th, 2013, 1:18pm)

Title: kth largest element from the 2-d array
Post by spur on Feb 10^th, 2013, 1:18pm

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

Title: Re: kth largest element from the 2-d array
Post by birbal on Mar 14^th, 2013, 9:13am

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.

Title: Re: kth largest element from the 2-d array
Post by Grimbal on Mar 15^th, 2013, 9:59am

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.

Title: Re: kth largest element from the 2-d array
Post by Spicyy on Apr 5^th, 2013, 11:32am

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 :(

Title: Re: kth largest element from the 2-d array
Post by Grimbal on Apr 7^th, 2013, 7:41am

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