@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 Top(int *); // O(1)
// This will remove the root element from the heap
// and readjust the heap.. O(1) + O(log N)
void RemoveTop(int *);
// Insert an element into the heap..
void Insert(int * heapArr, int elem); // O(log N)
// As i have mentioned in the previously posted solution that
// we going to store the indices instead of the actual element..
Insert(MinH, 0);
Insert(MaxH, 0);
int diff = 0;
for( int j =1; j < N; ++j)
{
Insert(MinH, j);
Insert(MaxH, j);
diff = A[Top(MaxH)] - A[Top(MinH)];
if (diff <=K)
{
if (diff > currMax)
{
currMax = diff;
strtInd = currStartInd;
endInd = j -1;
}
}
else
{
if ( A[j] == A[Top(MaxH)] )
{
currStartInd = Top(MinH) +1;
Remove(MinH);
while(MinH is not empty)
{
if (Top(MinH) < currStartInd)
Remove(MinH);
else if (A[Top(MaxH)] - A[Top(MinH)] <= K)
break;
else
{
currStartInd = Top(MinH) +1;
Remove(MinH);
}
}
}
else
{
// vice-versa based on the above logic..
}
}
}
On Jan 2, 8:28 pm, top coder <[email protected]> wrote:
> @Lucifer
>
> In your algo: how do we get the starting index of the subarray i.e
> result?
>
> On Jan 1, 11:03 pm, Lucifer <[email protected]> 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 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 Y[N] can be used to implement the max-
> > heap
>
> > Instead of having a min and max variable, for calculating the
> > difference we will use:
> > a) Top(MinH)
> > b) Top(MaxH)
>
> > Hence, the difference calculation would be :
> > Top(MaxH) - Top(MinH)
>
> > Say, the current processed element is A[i], then we will insert the
> > same in both MinH and MaxH.
>
> > 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 work as given the index we can always retrieve
> > the actual value i.e. A[i]..
>
> > Once inserted we will do the diff calculation as previous and see if
> > its <= K.
>
> > Now, currentStrInd = 0 for the longest subarray is 0,
>
> > Once the diff > K, then we will do the following to get the next
> > currentStrInd ...
>
> > Say, the at A[j] the diff > K,
>
> > If A[j] = A[Top(MaxH)], that means we need to get the reinitialize the
> > start index of the subarray based on the next min elements..
> > {
> > // First we will initialize currentStrInd,
>
> > currentStrInd = Top(MinH) +1;
>
> > pop(Top(MinH)); // this operation is basically removing the top and
> > re-adjusting the heap .. O(log N)
>
> > while(MinH is not empty)
> > {
> > if (Top(MinH) < currentStrInd)
> > pop(Top(MinH)) ;
>
> > else if (A[Top(MaxH)] - A[Top(MinH)] <= K)
> > break;
>
> > else
> > {
> > currentStrInd = Top(MinH) +1;
> > pop(Top(MinH));
> > }
> > }}
>
> > else
> > {
> > // vice-versa..
>
> > }
>
> > Now,
> > The outer loop will run from j = 1 to N ...This is nothing but
> > accessing the elements sequentially..
>
> > Also a particular element will be inserted and removed from the MinH
> > and MaxH only once.
> > Insertion and deletion(along with readjusting the heap) is an O(log n)
> > operation..
> > Now the total no. of elements that a heap can store is N..
>
> > Hence, for N elements to be inserted and removed from a heap the total
> > operation
> > over the entire run of the algo would be N log N..
>
> > Now, if u observe closely the heaps are used for resetting the
> > currentSrtIndex..
>
> > Hence, the total work load of the entire algo would be O(N Log N)...
>
> > ---------------------------------------
>
> > On Jan 1, 7:54 pm, atul anand <[email protected]> wrote:
>
> > > Lucifier : i didnt read your second approach ..but yeah i have implemented
> > > the same.
> > > nice :)
>
> > > did u come up with NlogN approach??- Hide quoted text -
>
> > - Show quoted text -
--
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.
