@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 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 <atul.87fri...@gmail.com> 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
