@mohit can u plz explain ur algo with an example On Sun, Dec 19, 2010 at 8:15 PM, Ankur Khurana <ankur.kkhur...@gmail.com>wrote:
> how about sorting the array in an auxillary array first. then compare > the elements in sorted and un sorted array. the first elements to > differ from start and end in unsorted array constitute the sub array > we are finding. i dont know this solution seems to easy , it might be > wrong. Any comments ? > > On Sun, Dec 19, 2010 at 8:03 PM, Ankur Murarka > <ankur.murarka....@gmail.com> wrote: > > Doesnt the time complexity seem to be a li'l large?? Looks like its > taking > > exponential time... > > > > On Sun, Dec 19, 2010 at 5:01 PM, mohit ranjan <shoonya.mo...@gmail.com> > > wrote: > >> > >> Let A[0..n] be the array > >> > >> > >> Step 1: Start from A[0] and find out the first element, beyond which > array > >> in not sorted, let's call it A[j] > >> Step 2: Start from A[n], move backward and find first element beyond > which > >> array in not sorted, let's call it A[k] > >> > >> so we have > >> A[0]....A[j].....A[k]....A[n] > >> -------------- -------------- > >> sorted sorted > >> > >> > >> now scan A[j] to A[k], and find any element that is smaller than any > >> number in A[0]-A[j], if any element is found, mark it as new j > >> similarly scan A[j]-A[k] and find any element that is larger than any > >> number in A[k]-A[n], if any element is found, mark it as new k > >> > >> final j and k are the answer... > >> > >> > >> > >> Mohit > >> > >> > >> > >> On Sun, Dec 19, 2010 at 2:32 AM, Dan <dant...@aol.com> wrote: > >>> > >>> On Dec 18, 9:57 am, snehal jain <learner....@gmail.com> wrote: > >>> > Given an unsorted array arr[0..n-1] of size n, find the minimum > length > >>> > subarray arr[s..e] such that sorting this subarray makes the whole > >>> > array sorted. > >>> > >>> > >>> Sounds like a simple homework problem to me. :-) > >>> > >>> -- > >>> You received this message because you are subscribed to the Google > Groups > >>> "Algorithm Geeks" group. > >>> To post to this group, send email to algoge...@googlegroups.com. > >>> To unsubscribe from this group, send email to > >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > >>> 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 algoge...@googlegroups.com. > >> To unsubscribe from this group, send email to > >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > >> 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 algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > > 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 algoge...@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.