any element to the right of X in the same array is less than X. Any element to the top of X in the same column is less than X. so any element to the nrth east of X is less than X.
All the elements to the south west, (including X) are not less than X. To the north west is a mix and to the south east there is a mix. So if we take a big north east, which leaves out only 2n-1 elements in the L they ought to be the largest. this is the same argument when u analyze the order statistics worst case O(n) bound. And this is the same argument u give when given 2 arrays of size N ( not sorted) u want to find whether there could be a sum =some constant C in O(NlogN) time becuas esorting takes NLogN. arrange one array as ascending(Y axis) and one descending(X axis). and form the grid. Property being any element X has its north east contaisn all the elements which are strickely less. and its south west, including it contaisn all elements which are greater than or equal to X. So we start from the top left hand corner and making our entire search start such that the N^2 sums form the south east ( where there is a mix) an then we go downwards if we need a bigger sum, and rightwards if we need a smaller sum. Since the north east and south west is clearly partitioned across any sum u r pointing to right now, and u have already ensured through ur operations that ur north west doesnt contain the sum of ur interest, u proceed south east and never travel back, making a total of 2N moves in the worst case. Its a similar argument. On Mon, Jul 26, 2010 at 2:25 PM, manish bhatia <[email protected]> wrote: > How are we making sure that top n-elements would lie in this 'L' shaped > array? > > Also, why don't we take an extreme case, such that the origin is > bottom-left element of the grid, then we have only 2n-1 elements to chose n > biggest elements from. > > So, can we prove that taking Ist quardrant as (n-2)x(n-3) would leave > n-biggest out? What is the criterion to chose the Ist quardrant? > > manish... > > > ------------------------------ > *From:* topojoy biswas <[email protected]> > *To:* [email protected] > *Sent:* Thu, 22 July, 2010 10:10:58 AM > > *Subject:* Re: [algogeeks] a google question > > im sry the L should look like this: > > > > 10 9 8 5 3 2 1 > 7 17 16 > 8 18 17 > 9 19 18 > 10 20 19 > 11 21 20 19 16 14 13 12 > 12 22 21 20 17 15 14 13 > 13 23 22 21 18 16 15 14 > > > I missed a row in the last mail. > > On Thu, Jul 22, 2010 at 10:03 AM, topojoy biswas <[email protected] > > wrote: > >> consider these arrays: >> >> 10 9 8 5 3 2 1 >> >> and >> >> 13 12 11 10 9 8 7 >> >> >> form a grid like this: >> >> 10 9 8 5 3 2 1 >> 7 17 16 15 12 10 9 8 >> 8 18 17 16 13 11 10 9 >> 9 19 18 17 14 12 12 10 >> 10 20 19 18 15 13 12 11 >> 11 21 20 19 16 14 13 12 >> 12 22 21 20 17 15 14 13 >> 13 23 22 21 18 16 15 14 >> >> basically have an array descending and have one array ascending. >> >> If you add them in a grid, check that for any sum, all sums to its right >> are less than it( in the same row), al sums above it( in the same column) >> are less than it, all sums below it( in the same row) are greater than it. >> >> 10 9 8 5 3 2 1 >> 7 17 16 15 *12 10 9 8* >> 8 18 17 16 *13 11 10 9* >> 9 19 18 17 *14 12 12 10* >> 10 20 19 18 *15 13 12 11* >> 11 *21 20 19* 16 14 13 12 >> 12 *22 21 20* 17 15 14 13 >> 13 *23 22 21* 18 16 15 14 >> >> So all sums which form the first quadrant origining at 19 are less than >> 19. >> >> And the 3rd quadrant formed by origining 19 including 19 are strickedly >> grater than or equal to 19. >> >> This means in the added array will look like this: >> __________________________________________________________ >> |________________|___________________|______________________| >> <-------x----------><------m---------------><-----------------y---------> >> >> x = no of elements in the underlined first quadrant >> y= no of elements in the 3rd quadrant excluding 19. >> m= the number of elements in the 2nd and the 4th quadrant including 19. >> >> So 19 would lie some whr in the 2n slot of this divided aray picture. >> >> So if we make x big enough so that m+y is small enough=O(n), we will >> reduce our load. >> >> so choose x=(n-2)(n-3) which means something like this: >> <------(n-2)-------> >> 10 9 8 5 3 2 1 >> 7 17 16 15 12 10 9 8 --------------- >> 8 18 17 16 13 11 10 9 >> 9 19 18 17 14 12 12 10 (n-3) >> 10 20 19 18 15 13 12 11 ----------------- >> 11 21 20 19 16 14 13 12 >> 12 22 21 20 17 15 14 13 >> 13 23 22 21 18 16 15 14 >> >> Then we will be left with an array of size m+y=5n-6 which is >n for all n >> >2 like this: >> >> 10 9 8 5 3 2 1 >> 7 17 16 >> 8 18 17 >> 9 19 18 >> 10 20 19 >> 11 21 20 >> 12 22 21 20 17 15 14 13 >> 13 23 22 21 18 16 15 14 >> >> Till this point it takes constant time. >> >> Now the first column of the "L" formed is sorted. So is the 2nd column. >> >> So is the horizonal part of L which is comprized of two sorted arays >> (20-13) and (21-14). >> >> All of the elements add to 5n-6. We can merge sort them in O(n) time. Take >> the biggest n elements. >> >> >> >> >> >> On Mon, Jul 19, 2010 at 12:18 PM, ankur aggarwal < >> [email protected]> wrote: >> >>> >>> >>> this ques was asked by google.. i* could find any gud soln than order n*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]<algogeeks%[email protected]> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> Topo. >> >> There are days when solitude is a heady wine that intoxicates you with >> freedom, others when it is a bitter tonic, and still others when it is a >> poison that makes you beat your head against the wall. ~Colette >> > > > > -- > Topo. > > There are days when solitude is a heady wine that intoxicates you with > freedom, others when it is a bitter tonic, and still others when it is a > poison that makes you beat your head against the wall. ~Colette > > -- > 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]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- > 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]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- 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.
