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