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
--
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.
