@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 <topcode...@gmail.com> 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 <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.