minimum-operations-to-sort-a-permutation.cpp (2068B)
1 class Solution { 2 public: 3 int minOperations(vector<int>& nums) { 4 // permutation of n-1 5 // this means 0 -> n is the sorted 6 7 // ops: 8 // reverse array 9 // rotate left by one 10 11 // return min op count or -1 12 13 // idea: 14 // we just rotate left by one until it matches the n-1 -> 0 array 15 // then return ops + 1 16 // are there cases where we invert first? 17 // inversion makes sense to go to right 18 // since these are all in one, 19 // we might want to try both ways? 20 21 // check if there's a monotonically increasing walk with at most one exclusion 22 23 int idxZero = -1; 24 int maxIdx = -1; 25 26 for(int i = 0; i < nums.size(); ++i) { 27 if(nums[i] == 0) { 28 idxZero = i; 29 } 30 if(nums[i] == nums.size() - 1) { 31 maxIdx = i; 32 } 33 } 34 35 bool monoLeft = true; 36 bool monoRight = true; 37 38 for(int i = idxZero+1; i < nums.size() + idxZero; ++i) { 39 if(nums[i % nums.size()] < nums[(i+nums.size() - 1) % nums.size()]) { 40 monoRight = false; 41 break; 42 } 43 } 44 45 if(!monoRight) { 46 for(int i = maxIdx + 1; i < nums.size() + maxIdx ; ++i) { 47 if(nums[i % nums.size()] > nums[(i+nums.size() - 1) % nums.size()]) { 48 cout << nums[i % nums.size()] << endl; 49 cout << nums[(i+nums.size() - 1) % nums.size()] << endl; 50 return -1; 51 } 52 } 53 } 54 55 int n = nums.size(); 56 57 if(monoRight) { 58 int shiftLeftCost = idxZero; 59 int shiftRightCost = (n - idxZero) + 2; 60 return min(shiftLeftCost, shiftRightCost); 61 } else { 62 int shiftLeftCost = maxIdx + 1; 63 int shiftRightCost = 1 + (n - maxIdx) % n; 64 return min(shiftLeftCost, shiftRightCost); 65 } 66 return 0; 67 } 68 };