algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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 };