Minimize unsorted segment

Given an array of integers, write a method to find indices m and n such that if you sorted elements m through n, the entire array would be sorted. Minimize n-m (That is, find the smallest such sequence).

Example

Input: {1, 2, 4, 7, 10, 11, 7, 12, 6, 7, 16, 18, 19}

Output: {3, 9}

C++:
01 void minUnsortedSeg(int* A, int size, int& start, int& end)
02 {
03     int* B=new int[size];
04     int* C=new int[size];
05     int max=A[0];
06     for(int i=0;i<size;i++){
07         if(A[i]>max)
08             max=A[i];
09         B[i]=max;
10     }
11     int min=A[size1];
12     for(int i=size1;i>=0;i){
13         if(A[i]<min)
14             min=A[i];
15         C[i]=min;
16     }
17     start=0;
18     for(int i=0;i<size1;i++){
19         if(A[i]==C[i]){
20             start++;
21         }
22         else
23             break;
24     }
25     end=size1;
26     for(int i=size1;i>start;i){
27         if(A[i]==B[i])
28             end;
29         else break;
30     }
31 }
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s