forked from Ritesh25696/interviewBit
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathMaximum Unsorted Subarray
101 lines (84 loc) · 2.04 KB
/
Maximum Unsorted Subarray
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
You are given an array (zero indexed) of N non-negative integers, A0, A1 ,…, AN-1.
Find the minimum sub array Al, Al+1 ,…, Ar so if we sort(in ascending order) that sub array, then the whole array should get sorted.
If A is already sorted, output -1.
Example :
Input 1:
A = [1, 3, 2, 4, 5]
Return: [1, 2]
Input 2:
A = [1, 2, 3, 4, 5]
Return: [-1]
In the above example(Input 1), if we sort the subarray A1, A2, then whole array A should get sorted.
See Expected Output
**************************************************************************************************************************
vector<int> Solution::subUnsort(vector<int> &A) {
vector<pair<int,int>> input;
vector<int> result;
for(int i=0 ;i<A.size() ; i++){
input.push_back(make_pair(A[i],i));
}
sort(input.begin(),input.end());
int start = 0;
int end = input.size()-1;
while(input[start].second == start && start < input.size()){
start++;
}
if(start == input.size()) {
result.push_back(-1);
return result;
}
while(input[end].second == end && end >= 0){
end--;
}
result.push_back(start);
result.push_back(end);
return result;
}
********************************************************************************************
vector<int> Solution::subUnsort(vector<int> &arr) {
int n = arr.size();
int s = 0, e = n-1, i, max, min;
vector<int> result;
for (s = 0; s < n-1; s++)
{
if (arr[s] > arr[s+1])
break;
}
if (s == n-1)
{
result.push_back(-1);
return result;
}
for(e = n - 1; e > 0; e--)
{
if(arr[e] < arr[e-1])
break;
}
max = arr[s]; min = arr[s];
for(i = s + 1; i <= e; i++)
{
if(arr[i] > max)
max = arr[i];
if(arr[i] < min)
min = arr[i];
}
for( i = 0; i < s; i++)
{
if(arr[i] > min)
{
s = i;
break;
}
}
for( i = n -1; i >= e+1; i--)
{
if(arr[i] < max)
{
e = i;
break;
}
}
result.push_back(s);
result.push_back(e);
return result;
}