I think this can be done in O(n) time simply by finding the median of elements at DIAGNOL starting from right corner to left corner. Coz as elements are sorted row-wise and column-wise , it implies that elements below this diagonal are all greater than elements on this diagonal and all above this are smaller. So say for above example : 3 >3<4 , means median is 3.
On Sat, Nov 5, 2011 at 1:59 AM, Gene <[email protected]> wrote: > Here's an idea. Say we pick any element P in the 2D array A and use > it to fill in an N element array X as follows. > > j = N; > for i = 1 to N do > while A(i, j) > P do > j = j - 1; > end; > X(i) = j; > end; > > This algorithm needs O(N) time. > > The elements of X split each row with respect to P. That is, for each > i = 1 to N, > > A(i, j) <= P if 0 < j <= X(i), A(i,j) > P if X(i) < j <= N. > > Now the strategy is to create two length N arrays a = [0,0,...0]; and > b = [N,N,...]. We'll maintain the invariant that a[i] < Median <= b[i] > for some i. I.e, they "bracket" the median. > > We define functions L(a) = sum_i( a(i) ) and R(b) = sum_i( N - > b(i) ). These tell us how many elements there are left and right of > the bracket. > > Now reduce the bracket as in binary search: Guess a value P, compute > X. If L(X) >= R(X), set b = X else set a = X. > > Keep guessing new P values in a way that ensures we reduce the number > of elements between a and b by some fixed fraction. If we can do > that, we'll get to 1 element in O(N log N) time. > > The remaining problem is picking good P's. Certainly the first time is > easy. Just take A(N/2, N/2). This has approximately (at least) N^2/4 > elements larger than it and N^2/4 smaller due to the sorted rows and > columns. This is what we need to get O(N log N) performance. > > But after the first split, things get trickier. The area between a and > b takes on the shape of a slash / /, so you can't just pick a P that > moves a and b together by a fixed fraction of remaining elements. > > Not to worry! You can quickly look up the (at most) N row medians in > the bracket, i.e. > > { A(i, (a[i] + b[i] + 1) / 2) | a[i]<b[i] , i = 1 to N } > > and use the well known O(N) median selection algorithm to get a median > of this. This has the quality we want of being somewhere roughly in > the middle half of the remaining elements. The logic is the same as > the selection algorithm itself, but in our case the rows are pre- > sorted. > > In all, each partitioning step requires O(N), and a fixed fraction > (about 1/2) of the elements will be eliminated from the bracket with > each step. Thus O(log n) steps will be needed to bring the bracket to > size 1 for an overall cost of O(N log N). > > I don't doubt that there's a simpler way, but this one seems to work. > Anyone see problems? > > On Nov 3, 3:41 pm, sravanreddy001 <[email protected]> wrote: > > any better solution than O(N^2) in worst case? > > How do we take advantage of sorting and find in O(N lg N) > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Mohit -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
