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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
