simple and nice! n log n time... I however believe there's a way to get the solution in O(n) time...
On Dec 19, 6:45 am, 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. > >>> 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. > > > -- > > 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. -- 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.
