-
Notifications
You must be signed in to change notification settings - Fork 0
/
Even Swap
49 lines (33 loc) · 1.46 KB
/
Even Swap
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
https://practice.geeksforgeeks.org/contest/interview-series-44/problems/#
Edutorial : https://www.youtube.com/watch?v=AWyGB-P90sg
class Solution
{
public:
vector <int> lexiographicallyLargest(vector <int> &a,int n)
{
// O(N^2)
// vector<int> b(n);
// for(int i=0;i<n; i++){
// for(int j=n-2;j>= i ;j--){
// if(a[j + 1] > a[j] and (a[j + 1] + a[j])% 2 == 0)swap(a[j], a[j+1]);
// return b;
// }
// b[i] = a[i];
// }
// O(NlogN)
// find maximum even and odd elements subarrays -> sort in desc
int i = 0, j = 0;
// i -> window starting point
// j -> iteration
while(j < n){
if((a[i]&1) == (a[j]&1))j++;// if same parity, increase the window size
else{// we hit the breaking point -> odd to even or even to odd
// sort that subarray in desc order
sort(a.begin() + i , a.begin() + j, greater<int>());
i=j;// move previous window starting point i to the next window starting point j
}
}
sort(a.begin() + i , a.end(), greater<int>());
return a;
}
};