Another O(1) space O(N) time solution, 24MS, idea is swapping block by block


  • 0
    S

    Idea is swapping the k-element block to the left, each time 1 block is swapped.
    If some elements are remained at the left rotate these element to the right and vice - versa.

      class Solution {
      public:
          void rotate(vector<int>& nums, int k) {
              k = k % nums.size();
              if( k==0) return;
              rotateRight(nums, k, 0, nums.size()-1);
          }
      private:
          void rotateLeft(vector<int>& nums, int k, int start, int end)
          {
              int t = start;
              int remaining = end-start+1-k;
              while(remaining>=k)
              {
                  for(int i=t; i< t+k; i++)
                      swap( nums[i], nums[i+k] );
                  remaining -= k;
                  t+=k;
              }
              if(remaining > 0)
                  rotateRight(nums, remaining, end-remaining-k+1, end);
          }
    
          void rotateRight(vector<int>& nums, int k, int start, int end)
          {
              int t = end - k +1;
              int remaining = t-start;
              while(remaining>=k)
              {
                  for(int i=t; i< t+k; i++)
                      swap( nums[i], nums[i-k] );
                  remaining -= k;
                  t -= k;
              }
              if(remaining > 0)
                  rotateLeft(nums, remaining, start, start+remaining+k-1);
          }
      };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.