parse the document for the words and maintain a position table position table should be like this: w1-> p1 p2 p3....pn w2->x1 x2 x3 ....xn .... k lists O(n) if hashing is used
now go to begining of list and findout the maximum position say 'start' O(k) similarly from end of all list , check for the min, say 'end' O(k) check if [start, end] is the necessary interval to avoid corner cases I think this should be done in O(n) so overall it is O(n) ? On Dec 2, 2:39 pm, surender sanke <[email protected]> wrote: > Hi > how about finding this for an integer array and finding i and j such that > Min(j-i) > > surender > On Fri, Dec 2, 2011 at 3:09 AM, sravanreddy001 > <[email protected]>wrote: > > > > > > > > > An idea is to start with a heap of size k. > > Its tricky how to keep track of the start and end indices of the smallest > > length. Do not enter a duplicate element in the heap. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To view this discussion on the web visit > >https://groups.google.com/d/msg/algogeeks/-/XbqIrf1Z6MUJ. > > 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. -- 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.
