1337yogesh
BAN USERtry {1,2,9,4,4,4};
correct output should be 9 4 4 4
doesn't seem correct to me.
try input as the following array --> {1,1,1,1,1};
Sorting will take atleast O(N LogN) Time in the worst case.
Copying will take atleast O(N) Space.
Time Complexity O(N)
Space Complexity O(1)
Following is the code written in C++
Just include the header files and copy paste the code.
Let me know if there are bugs :P
int
find_min_array (int* a, int s, int e);
int
find_max_array (int* a, int s, int e);
void
find_min_subarray_sort(int* a, int sidx, int eidx);
int main ()
{
int *a;
cout<<"enter the number of elements to fill in the array\n";
int n;
cin>>n;
a=new int[n];
cout<<"Fill the array with "<<n<<" elements\n";
for (int i =0;i<n;i++)
cin>>a[i];
// Now find min subarray in O(N) time
find_min_subarray_sort (a,0,n-1);
return 0;
}
void
find_min_subarray_sort(int* a, int sidx, int eidx)
{
int s = sidx;
int e = eidx;
int first;
int last;
int i;
for(i=s;i<e;i++)
{
if(a[i]>a[i+1])
break;
}
first = i;
if (first == eidx)
{
cout<<"array is already sorted\n";
return;
}
for(i=e;i>s;i--)
{ if(a[i] < a[i-1])
break;
}
last = i;
int min = find_min_array (a, first+1, last);
// Where to fit this min from 0 to first? We can do a Binary search here, but that will not change the complexity. Doing linear search for now
for(i=0;i<=first;i++)
{
if(min<a[i])
break;
}
cout<<"Min Subarray is the following (Indices start from 0): "<<endl;
cout<<"Start Index: "<<i<<endl;
int max = find_max_array (a, first, last-1);
// Where to fit this max from last to n-1?We can do a Binary search here, but that will not change the complexity. Doing linear search for now
for(i=eidx;i>last;i--)
{
if(max>a[i])
break;
}
cout<<"End Index: "<<i<<endl;
}
int
find_min_array (int* a, int s, int e)
{
int min=a[s];
for(int i=s+1;i<=e;i++)
{
if(a[i]<min)
min = a[i];
}
return min;
}
int
find_max_array (int* a, int s, int e)
{
int max=a[s];
for(int i=s+1;i<=e;i++)
{
if(a[i]>max)
max = a[i];
}
return max;
}
try your solution with input as the following
{-17, -13, -5, 5, 9, 12, 16, 23}
try {1,1,-2,3,4,5};
- 1337yogesh September 19, 2014output should be:
Start Index=0
End Index=2
but I think yours will give start index as 1