@Lucifier :
i was considering algo as mentioned by you and was considering heap with
indexes as mentioned in your first post i.e :-
/*
Also, though the MinH and MaxH is designed based on the element values
i.e A[i], but we will store only the index of the element i.e. 'i'.
// The above app will
@atul..
you are not getting it wrong.. Its absolutely correct
On Jan 5, 11:28 pm, atul anand atul.87fri...@gmail.com wrote:
@Lucifier :
i was considering algo as mentioned by you and was considering heap with
indexes as mentioned in your first post i.e :-
/*
Also, though the MinH
your algo wont work for a[]={8,11,2} with k=7.
acc to u,ans should be 3,but it is 2.
you are not considering the diff between max and min value
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
@all
sorry for my prev post.
On Jan 5, 12:42 am, gaurav bansal gbgaur...@gmail.com wrote:
your algo wont work for a[]={8,11,2} with k=7.
acc to u,ans should be 3,but it is 2.
you are not considering the diff between max and min value
--
You received this message because you are subscribed
@atul..
First of all 6 is not in the heap but its index '0' is..
I think before also u had raised this question of heap stability and i
did explain with an example in one of my previous posts that it won't
affect the checks...
I m repeating the same explanation here with the reason why it won't
when i made changes to the inner loop - from for (j = N; j 0; --j) to
for (j = *N-1*; j 0; --j)
and endind = j-1; to endind = j;
i am getting same output:-
but for input : - 6,7,1,10,3,7,2,5,9
K=8
output : start = 0 , end = 8
below code is fine after fixing??
correction :-
when i made changes to the inner loop - from for (j = N; j 0; --j) to
for (j = *N-1*; j 0; --j)
and endind = j-1; to endind = j;
i am getting *right* output:-
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
@Lucifier : for your heap approach here is my concerns :-
input :- 6,10,8,5,9,7,1,5,4
K=8;
min heap=1,5,6,7,8,9,10
max heap=10,9,8,6,7,5,1
A[Top(MaxH)] - A[Top(MinH)] K i.e 10-1 8
A[j] = A[Top(MinH)];
currentStrInd = Top(MaxH) +1; // currentStrInd=2
pop(Top(MaxH));
(now , max heap=
@above : correction...
while(MaxH is not empty)
{
if (Top(MaxH) currentStrInd)// *4(index of 9) 2 *-move
to else if condition
pop(Top(MaxH)) ;
else if (A[Top(MaxH)] - A[Top(MinH)] = K) -- *9-1 = 8* TRUE
.break this loop.
break;
}
--
You received this
@atul...
For the O(n^2) approach, here's the working code..It should work for
all ur examples.. I have fixed it..
int max = 0;
int strtind = -1;
int endind = -1;
int X[2][N];
for(int i=0;i=N;i++)
X[0][i]=X[1][i] = 0;
int *prev, *curr;
for (int i = 0; i N; ++i)
{
prev = X[i%2];
curr =
@Lucifier : it didnt work as you can see
input :- 6,10,8,5,9,7,1,5,4
K=8;
min heap=1,5,6,7,8,9,10
max heap=10,9,8,6,7,5,1
A[Top(MaxH)] - A[Top(MinH)] K i.e 10-1 8
//we are in else part of your logic
A[j] = A[Top(MinH)];
currentStrInd = Top(MaxH) +1; // currentStrInd=2
pop(Top(MaxH));
@Lucifier : great :) :) ... your new fixed code it working perfectly .
but it would be great if you give little explanation of this updated code
On Tue, Jan 3, 2012 at 2:56 PM, atul anand atul.87fri...@gmail.com wrote:
when i made changes to the inner loop - from for (j = N; j 0; --j) to
this is like a DP problem to me
1) build a 2 D array .
2) store If difference b/w any two number is = K then M[i,j]=1
else M[i,j]=0
3) Now find max size square (containing all ones) by using Dynamic
Programming.
PRAVEEN RAJ
DELHI COLLEGE OF ENGINEERING
--
You received this message
@Lucifer
In your algo: how do we get the starting index of the subarray i.e
result?
On Jan 1, 11:03 pm, Lucifer sourabhd2...@gmail.com wrote:
@atul..
Below i have explained how the reduction from N^2 to N log N approach
will work..
Space complexity 2*N = O(N)
The following data
@topcoder..
Below i have added a semi pseudocode for better understanding..
Let me know if u want further explanation..
int currMax = 0;
int strtInd = -1;
int endInd = -1;
int currStartInd = 0;
int MinH[N];
int MaxH[N];
// this will return the value of the root stored in the heap..
int
@praveen : i guess we can optimize the space to O(n);
if diff b/w two number is =K then A[i]=A[i-1]+1;
if condition fails temp_maxLen=A[i-1];
if(temp_maxlen maxLen)
{
maxLen=temp_maxlen;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
@atul..
Say the array is
2 4 6 8 10 and diff is 2.
A = 1 1 1 1 1 which is incorrect..
Or may be the above code explains something else..
If so, can u give more explanation...
On Jan 3, 12:03 am, atul anand atul.87fri...@gmail.com wrote:
@praveen : i guess we can optimize the space to O(n);
@above..
I m sorry,
A would be 1 2 3 4 5 ..
On Jan 3, 12:03 am, atul anand atul.87fri...@gmail.com wrote:
@praveen : i guess we can optimize the space to O(n);
if diff b/w two number is =K then A[i]=A[i-1]+1;
if condition fails temp_maxLen=A[i-1];
if(temp_maxlen maxLen)
{
I think this can be solved in NlogN using binary search
Here is the idea
We take a deque which stores the index of the array in increasing order
i.e. the index with minimum value is always on the front of the deque
Now when a new element comes we check with the front of this deque .
If the
@Ankur..
A : 2 4 6 8 1, diff is 6.
Looks like the answer acc. to ur code would be 5, but actually it
should be 4..
I m correct, then it can be fixed by looking at the front and back of
the queue and see whether the A[i] is actually the curr min or curr
max..
And then calculate the diff based
@Lucifer
I checked with my code
The answer is coming out to be 4 ..So in this case its passing
Also the queue is containing the indexes in order of increasing values ..so
for curr min we need to only check the front of the queue.
Also I remove the elements of the queue till all the diff of
@Ankur..
I just executed ur code and i m getting 5, instead of 4..
Also,
*
Then yesit is possible that i j and i k... but a[i] is always
less
than a[j] and a[k]...
*
Yes u r right.. but, then when u are calculating the size u are also
by default including the element at index K which
@Lucifer
I checked again and saw a few flaws in my code . Please ignore my prev post
.. :P
1) I am always comparing with q.front() and taking the diff but I should
also do the same with q.back() as it might contain values which have diff
k . So yes , this is a bug
For this as you rightly
@ Ankur,,
Also, in the statement..
*
Then yesit is possible that i j and i k... but a[i] is
always
less
than a[j] and a[k]...
*
* but a[i] always less* - by a[i] i meant the latest element accessed
and not the element positioned at Q.front which is nothing but element
at index 'i'
Hence,
@Ankur..
Missed ur post just by 2 mins..
Great..
-
On Jan 3, 3:59 am, Lucifer sourabhd2...@gmail.com wrote:
@ Ankur,,
Also, in the statement..
*
Then yes it is possible that i j and i k... but a[i] is
always
less
than a[j] and a[k]...
*
* but a[i] always
@Lucifier :
*if ( A[j] max)
{
max = A[j];
strtind = i - max + 1;*
i am not getting this in your code :-
say if input is :- 1,2,3,4,5,6,100
K=8;
A[j]=100;
then
(100 max)
{
max=100;
* strtind= i - 100 +1;
}
*
On Tue, Jan 3, 2012 at 4:33 AM, Lucifer
@atul..
Again :) an editing mistake...
Instead of A[j] it should be X[j];
i.e.
*
if ( X[j] max)
{
max = X[j];
strtind = i - max + 1;
endind = j - 1;
}
*
On Jan 3, 10:11 am, atul anand atul.87fri...@gmail.com wrote:
@Lucifier :
*if ( A[j] max)
{
max = A[j];
For input..
6,7,1,5,4,10,8
K=8
Start - 0 , end - 6
It shud be start =0 , end = 4
On 3 Jan 2012 12:10, Lucifer sourabhd2...@gmail.com wrote:
@atul..
Again :) an editing mistake...
Instead of A[j] it should be X[j];
i.e.
*
if ( X[j] max)
{
max = X[j];
strtind = i - max + 1;
ok ...
@Lucifier i have optimized your code further so that there is no need to
check every element i.e to outer for loop..
so i have skipped elements if they can never be part of second maxLen
sequence if exits.
int find_seq(int arr[],int *start,int *end,int k,int n)
{
int maxLen=0;
int
@atul
Is the above code's optimization based on the 2nd approach that i have
mentioned above or is it something different..
In case, you are doing something else can u provide us with more
explanation so that it would be easier for everyone to understand the
code ...
On Jan 1, 3:55 pm, atul
Lucifier : i didnt read your second approach ..but yeah i have implemented
the same.
nice :)
did u come up with NlogN approach??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
@atul..
Below i have explained how the reduction from N^2 to N log N approach
will work..
Space complexity 2*N = O(N)
The following data structures will be used to optimize the same :-
1) a min-heap named MinH - say X[N] can be used to implement the min-
heap.
2) a max- heap named MaxH - say
@Lucifier :
for the else case;
suppose arr is 6,10,8,5,9,7,1,5,4,3K=8
at max =10 , min =1 condition will fail
A[j] = A[Top(minH)];
currentStrInd = Top(MaxH) +1; // currentStrInd = index of 8
pop(Top(MaxH));
now because of A[Top(MaxH)] - A[Top(MinH)] = K (9 -1= 8)condition in while
loop
if i am getting it right then i guess because heap is not stable i.e it
does not guarantee that if there is multiple same elements say 4,4,4,5,5,10
then doing extract min and extract max would may not give oldest index or
you can say that 1st occurance of those multiple same elements i.e
arr[]=
@atul..
There are no stability or access issues with the code..
Below i have given explanation for ur concerns...
--
a) I think ur first concern is a stable heap...
The heap might not be stable as u have mentioned.. but the code makes
it stable..
Hence, it
@atul...
The only reason behind storing the indices instead of actual element
values in the heap, as mentioned in my original post, was to resolve
the issues that u have brought up...
Cheers :)
On Jan 2, 11:08 am, Lucifer sourabhd2...@gmail.com wrote:
@atul..
There are no stability or access
O(N^2) approach..
---
Say the current start index is i..
Then starting from i keep track of the min and max element and ensure
that the diff of max and min is =K.
Say the diff exceeds at index j, then the current continuous subarray
size would be (j - i) and we
@above
Correction..
i can be = R... hence, which can be found as part of traversal..
Another addition:
I have explained the concept using A[j] to be max.. In case A[j] is
min, then we will take a similar approach keeping in mind that R will
be closest but in terms of finding the max element..
HNY 2012(IST) in between to all members and happy coding for 2012 may all
your compilation produce ZERO errors
On Sun, Jan 1, 2012 at 12:01 AM, Lucifer sourabhd2...@gmail.com wrote:
@above
Correction..
i can be = R... hence, which can be found as part of traversal..
Another addition:
I
*if (max - min k) //* this code is unreachable in the while loop.
break;
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
remove continue in while loop...then it will work fine.
On Sun, Jan 1, 2012 at 12:49 AM, atul anand atul.87fri...@gmail.com wrote:
*if (max - min k) //* this code is unreachable in the while loop.
break;
--
You received this message because you are subscribed to the Google Groups
start=0;
maxLen=0;
min=arr[0];
max=arr[0];
j=0;
for(i=1;in;i++)
{
if(arr[i] max)
max=arr[i];
else if(arr[i] min)
min=arr[i];
if( (max - min ) k maxLen ( i - j ) )
{
maxLen=i - j;
start=j;
@atul..
No need to remove continue.. 'continue' has been added for
optimization..
(max - min) K, should only be checked when either we get a new min
or max...
In case the current processed element is neither a good fit for max or
min then we need not check for the difference..
On Jan 1, 2:33
43 matches
Mail list logo
