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.
